Maximum entropy Gaussian approximation for the number of integer points and volumes of polytopes

Introduction

In this paper, we address the problems of computing the volume and counting the number of integer points in a given polytope. These problems have a long history, see for example, surveys [GK94], [DL05] and [Ve05], and, generally speaking, are computationally hard. We describe a maximum entropy approach which, in a number of non-trivial cases, allows one to obtain good quality approximations by solving certain specially constructed convex optimization problems on polytopes. Those optimization problems can be solved quite efficiently, in theory and in practice, by interior point methods, see [NN94].

(1.2) The maximum entropy approach

We propose a simple remedy to this naive Monte Carlo approach. Namely, by solving a convex optimization problem on $P$, we construct a multivariate geometric random variable $X$ such that

on $P$, see Theorem 3.1 for the precise statement.

Similarly, to estimate the number of 0-1 vectors in $P$, we construct a multivariate Bernoulli random variable $X$, such that (1.2.2) holds while (1.2.1) is replaced by

(1.2.3) The probability mass function of $X$ is constant on the set $P\cap\{0,1\}^{n}$ of 0-1 vectors in $P$.

In this case, $X=\left(x_{1},\ldots,x_{n}\right)$, where $x_{j}$ are independent Bernoulli random variables with expectations $\zeta_{j}$ such that $z=\left(\zeta_{1},\ldots,\zeta_{n}\right)$ is the unique point maximizing the value of the strictly concave function, the entropy of $X$,

see Theorem 3.3 for the precise statement.

Finally, to approximate the volume of $P$, we construct a multivariate exponential random variable $X$ such that (1.2.2) holds and (1.2.1) is naturally replaced by

(1.2.4) The density of $X$ is constant on $P$.

Condition (1.2.4) allows us to express the volume of $P$ in terms of the density of $Y=AX$ at $Y=b$, while (1.2.2) allows us to establish a Local Central Limit Theorem for $Y$ in a number of cases. In this case, each coordinate $x_{j}$ is sampled independently from the exponential distribution with expectation $\zeta_{j}$ such that $z=\left(\zeta_{1},\ldots,\zeta_{n}\right)$ is the unique point maximizing the value of the strictly concave function, the entropy of $X$,

on $P$, see Theorem 3.6 for the precise statement. In optimization, the point $z$ is known as the analytic center of $P$ and it played a central role in the development of interior point methods, see [Re88].

These three examples (counting integer points, counting 0-1 vectors, and computing volumes) are important particular cases of a general approach to counting through the solution to an entropy maximization problem (cf. Theorem 3.5) with the subsequent asymptotic analysis of multivariate integrals needed to establish the Local Central Limit Theorem type results.

Main results

on $P$. Let $B$ be the $d\times n$ matrix with the columns $\zeta_{1}a_{1},\ldots,\zeta_{n}a_{n}$. We approximate the volume of $P$ by the Gaussian formula

Suppose that for some $\lambda>0$ we have

Then there exists an absolute constant $\gamma$ such that the following holds: let $0<\epsilon\leq 1/2$ be a number and suppose that

approximates $\operatorname{vol}P$ within relative error $\epsilon$.

In Section 4, we apply Theorem 2.2 to approximate the volume of a multi-index transportation polytope, see, for example, [Y+84], that is, the polytope $P$ of $\nu$-dimensional $k_{1}\times\ldots\times k_{\nu}$ arrays of non-negative numbers $\left(\xi_{j_{1}\ldots j_{\nu}}\right)$ with $1\leq j_{i}\leq k_{i}$ for $i=1,\ldots,\nu$ with prescribed sums along coordinate hyperplanes $j_{i}=j$. We show that Theorem 2.2 implies that asymptotically the volume of $P$ is given by a Gaussian formula (2.1.1) as long as $\nu\geq 5$. We suspect that the Gaussian approximation holds as long as $\nu\geq 3$, but the proof would require some additional considerations beyond those of Theorem 2.2. In particular, for $\nu\geq 5$ we obtain the asymptotic formula for the volume of the polytope of polystochastic tensors, see [Gr92].

For $\nu=2$ polytope $P$ is the usual transportation polytope. Interestingly, its volume is not given by the Gaussian formula, cf. [CM07b].

In [Ba09], a much cruder asymptotic formula of $\operatorname{vol}P$ in terms of $e^{f(z)}$ was proved under much weaker assumptions.

(2.3) Gaussian approximation for the number of integer points

For a polytope $P$, defined by a system $Ax=b,x\geq 0$, we find the point $z=\left(\zeta_{1},\ldots,\zeta_{n}\right)$ maximizing

Compared to the case of volume estimates (Sections 2.1–2.2), we acquire an additive error which is governed by the arithmetic of the problem.

Suppose that for some $\lambda\geq 0$ we have

Then, for some absolute constant $\gamma>0$ and for any $0\leq\epsilon\leq 1/2$, as long as

where $r$ is the smallest radius of the ball $B_{r}$ such that the lattice points $B_{r}\cap\Lambda_{i}$ are distributed regularly in every section $B_{r}\cap\Cal{A}_{i}$ for $i=1,\ldots,d$.

In Section 5, we apply Theorem 2.4 to approximate the number of 1-margin multi-way contingency tables, see for example, [Go63] and [DO04], that is, $\nu$-dimensional $k_{1}\times\ldots\times k_{\nu}$ arrays of non-negative integers $\left(\xi_{j_{1}\ldots j_{\nu}}\right)$ with $1\leq j_{i}\leq k_{i}$ for $i=1,\ldots,\nu$ with prescribed sums along coordinate hyperplanes $j_{i}=j$. We show that Theorem 2.4 implies that asymptotically the number of such arrays is given by a Gaussian formula (2.3.1) as long as $\nu\geq 5$. We suspect that the Gaussian approximation holds as long as $\nu\geq 3$, but the proof would require some additional considerations beyond those of Theorem 2.4.

In [Ba09], a much cruder asymptotic formula with the main term $e^{g(z)}$ in the logarithmic order is shown to hold for the number of integer points in flow polytopes (a class of polytopes extending transportation polytopes for $\nu=2$). At our request, A. Yong [Yo08] computed a number of examples. Here is one of them, originating in [DE85] and then often used as a benchmark for various computational approaches: we want to estimate the number of $4\times 4$ non-negative integer matrices with row sums $220,215,93$ and 64 and column sums $108,286,71$ and 127. The exact number of such matrices is $1225914276768514\approx 1.23\times 10^{15}$. Framing the problem as the problem of counting integer points in a polytope in the most straightforward way, we obtain an over-determined system $Ax=b$ (note that the row and column sums of a matrix are not independent). Throwing away one constraint and applying formula (2.3.1), we obtain $1.30\times 10^{15}$, which overestimates the true number by about $6\%$. The precision is not bad, given that we are applying the Gaussian approximation to the probability mass-function of the sum of 16 independent random 7-dimensional integer vectors.

(2.5) Gaussian approximation for the number of 0-1 points

For a polytope $P$ defined by a system $Ax=b$, $0\leq x\leq 1$ (shorthand for $0\leq\xi_{j}\leq 1$ for $x=\left(\xi_{1},\ldots,\xi_{n}\right)$), we find the point $z=\left(\zeta_{1},\ldots,\zeta_{n}\right)$ maximizing

Suppose that for some $\lambda>0$ we have

and that for some $0<\alpha\leq 1/4$ we have

Then, for some absolute constant $\gamma>0$ and for any $0<\epsilon\leq 1/2$, as long as

We note that in [Ba08] a much cruder asymptotic formula with the main term $e^{h(z)}$ in the logarithmic order is shown to hold for the number of 0-1 vectors in flow polytopes.

In Section 5, we apply Theorem 2.6 to approximate the number of binary 1-margin multi-way contingency tables, see for example, [Go63] and [DO04], that is, $\nu$-dimensional $k_{1}\times\ldots\times k_{\nu}$ arrays $\left(\xi_{j_{1}\ldots j_{\nu}}\right)$ of ’s and $1$’s with $1\leq j_{i}\leq k_{i}$ for $i=1,\ldots,\nu$ with prescribed sums along coordinate hyperplanes $j_{i}=j$. Alternatively, the number of such arrays is the number of $\nu$-partite uniform hypergraphs with prescribed degrees of all vertices. We show that Theorem 2.6 implies that asymptotically the number of such arrays is given by the Gaussian formula (2.5.1) as long as $\nu\geq 5$. We suspect that the Gaussian approximation holds as long as $\nu\geq 3$, but the proof would require some additional considerations beyond those of Theorem 2.6.

Maximum entropy

We start with the problem of integer point counting.

Let us fix positive numbers $p$ and $q$ such that $p+q=1$. We recall that a discrete random variable $x$ has geometric distribution if

For the expectation and variance of $x$ we have

attains its maximum value on $P$ at a unique point $z=\left(\zeta_{1},\ldots,\zeta_{n}\right)$ such that $\zeta_{j}>0$ for $j=1,\ldots,n$.

which is finite for $\xi_{j}>0$ and equals $+\infty$ for $\xi_{j}=0$ (we consider the right derivative in this case). Therefore, if $\zeta_{j}=0$ for some $j$ then g\bigl{(}(1-\epsilon)z+\epsilon y\bigr{)}>g(z) for all sufficiently small $\epsilon>0$, which is a contradiction.

Suppose that the affine hull of $P$ is defined by a system of linear equations

Since $z$ is an interior maximum point, the gradient of $g$ at $z$ is orthogonal to the affine hull of $P$, so we have

and some $\lambda_{1},\ldots,\lambda_{d}$. Therefore, for any $x\in P$, $x=\left(\xi_{1},\ldots,\xi_{n}\right)$, we have

Substituting $\xi_{j}=\zeta_{j}$ for $j=1,\ldots,n$, we obtain

The last identity states that the probability mass function of $X$ is equal to $e^{-g(z)}$ for every integer point $x\in P$. ∎

The proof is a straightforward modification of that of Theorem 3.1.

Below we provide an informal justification for the Gaussian approximation formula (2.3.1).

Let $P$ be a polytope and let $X$ be a random vector as in Theorem 3.1. Suppose that $P$ is defined by a system $Ax=b,x\geq 0$, where $A=\left(\alpha_{ij}\right)$ is a $d\times n$ matrix of rank $d<n$. Let $Y=AX$, so $Y=\left(y_{1},\ldots,y_{d}\right)$, where

Moreover, the covariance matrix $Q=\left(q_{ij}\right)$ of $Y$ is computed as follows:

Assuming that the probability density of $Y^{\ast}$ does not vary much on $b+\Pi$ and that the probability mass function of $Y$ at $Y=b$ is well approximated by the integral of the density of $Y^{\ast}$ over $b+\Pi$, we obtain (2.3.1).

Next, we consider the problem of counting 0-1 vectors.

Let $p$ and $q$ be positive numbers such that $p+q=1$. We recall that a discrete random variable $x$ has Bernoulli distribution if

attains its maximum value on $P$ at a unique point $z=\left(\zeta_{1},\ldots,\zeta_{n}\right)$ such that $0<\zeta_{j}<1$ for $j=1,\ldots,n$.

Suppose now that $x_{j}$ are independent Bernoulli random variables with expectations $\zeta_{j}$ for $j=1,\ldots,n$. Let $X=\left(x_{1},\ldots,x_{n}\right)$. Then the probability mass function of $X$ is constant on $P\cap\{0,1\}^{n}$ and equal to $e^{-h(z)}$ for every $x\in P\cap\{0,1\}^{n}$. In particular,

(3.4) Comparison with the Monte Carlo method

Applying a similar logic as in Section 3.2, we obtain the Gaussian heuristic approximation of (2.5.1).

is the entropy of the Bernoulli distribution with expectation $\xi$ while

is the entropy of the geometric distribution with expectation $\xi$. One can suggest the following general maximum entropy approach, cf. also a similar computation in [Ja57].

Then $\phi(x)$ is a strictly concave continuous function on $\operatorname{conv}(S)$.

be the entropy of the probability distribution $\{p_{s}\}$ on $S$.

Continuity and strict concavity of $\phi$ follows from continuity and strict concavity of $H$. Similarly, uniqueness of $\mu$ follows from the strict concavity of $H$.

which is finite for $p_{s}>0$ and is equal to $+\infty$ for $p_{s}=0$ (we consider the right derivative), we conclude that for the optimal distribution $\mu$ we have $p_{s}>0$ for all $s$.

Suppose that $A$ is defined by linear equations

Writing the optimality conditions, we conclude that for some $\lambda_{0},\lambda_{1},\ldots,\lambda_{d}$ we have

Finally, we discuss a continuous version of the maximum entropy approach.

We recall that $x$ is an exponential random variable with expectation $\zeta>0$ if the density function $\psi$ of $x$ is defined by

The characteristic function of $x$ is defined by

attains its unique maximum on $P$ at a point $z=\left(\zeta_{1},\ldots,\zeta_{n}\right)$, where $\zeta_{j}>0$ for $j=1,\ldots,n$.

Suppose now that $x_{j}$ are independent exponential random variables with expectations $\zeta_{j}$ for $j=1,\ldots,n$. Let $X=\left(x_{1},\ldots,x_{n}\right)$. Then the density of $X$ is constant on $P$ and for every $x\in P$ is equal to $e^{-f(z)}$.

As in the proof of Theorem 3.1, we establish that $\zeta_{j}>0$ for $j=1,\ldots,n$. Consequently, the gradient of $f$ at $z$ must be orthogonal to the affine span of $P$. Assume that $P$ is defined by a system of linear equations

Therefore, for any $x\in P$, $x=\left(\xi_{1},\ldots,\xi_{n}\right)$, we have

In particular, substituting $\xi_{j}=\zeta_{j}$, we obtain

Therefore, the density of $X$ at $x\in P$ is equal to

A similar formula can be obtained for the exponential integral

The integral may converge even if $P$ is unbounded. We introduce

(3.7) The Gaussian heuristic for volumes

Below we provide an informal justification of the Gaussian approximation formula (2.1.1)

Let $P$ be a polytope and let $x_{1},\ldots,x_{n}$ be the random variables as in Theorem 3.6. Suppose that $P$ is defined by a system $Ax=b$, $x\geq 0$, where $A=\left(\alpha_{ij}\right)$ is a $d\times n$ matrix of rank $d<n$. Let $Y=AX$, so $Y=\left(y_{1},\ldots,y_{d}\right)$, where

In view of Theorem 3.6, the density of $Y$ at $b$ is equal to

Assuming that the distribution of $Y$ at $Y=b$ is well approximated by the Gaussian distribution, we obtain formula (2.1.1)

Volumes of multi-index transportation polytopes

We apply Theorem 2.2 to compute volumes of multi-index transportation polytopes. We begin our discussion with ordinary (two-index) transportation polytopes. Although Theorem 2.2 does not imply the validity of the Gaussian approximation here, two-index polytopes provide a simple model case of computations that we later use in the case of a larger number of indices.

For integers $m,n>1$ let us choose positive numbers $R=\left(r_{1},\ldots,r_{m}\right)$ and $C=\left(c_{1},\ldots,c_{n}\right)$ such that

and let us consider the polytope $P=P(R,C)$ of all $m\times n$ non-negative matrices $x=\left(\xi_{ij}\right)$ with the row sums $r_{1},\ldots,r_{m}$ and the column sums $c_{1},\ldots,c_{n}$. As is known, $P$ is a non-empty $(m-1)(n-1)$-dimensional polytope, also known as a transportation polytope, see, for example, [Y+84]. If $m=n$ and $R=C=\left(1,\ldots,1\right)$ then $P$ is the polytope of $n\times n$ doubly stochastic matrices, also known as the Birkhoff polytope. We note that the row and column sums are not independent, since the total sum of all row sums is equal to the total sum of the column sums. We define the affine span of $P$ by the following non-redundant system of linear equations:

In other words, we prescribe the sums of the first $m-1$ rows, the first $n-1$ columns, and the total sum of the matrix entries. We observe that every column $a$ of the matrix $A$ of the system (4.1.1) contains at most 3 non-zero entries (necessarily equal to 1), so $\|a\|\leq\sqrt{3}$.

Let $z=\left(\zeta_{ij}\right)$ be a matrix, $z\in P$, maximizing

To bound the eigenvalues of $q$ from below, we bound the eigenvalues of a simpler form

for some real $\alpha,\beta$, and $\omega$. Therefore, the restriction of $\hat{q}$ onto $L$ can be written as

for some absolute constant $\delta>0$ and all $\alpha,\beta$ and $\omega$, we conclude that the eigenvalues of $\hat{q}$ exceed

for some absolute constant $\delta>0$. Same holds for the eigenvalues of $q$ as long as the numbers $\zeta_{ij}$ are uniformly bounded away from 0.

We notice that the minimum eigenvalue of $q$ is too small to satisfy the conditions of Theorem 2.2. In fact, as Canfield and McKay have shown [CM07b], the volume of the Birkhoff polytope is not asymptotically Gaussian as $m=n\longrightarrow+\infty$, since there is a fourth-order correction akin to the Edgeworth correction. However, a very similar analysis can be applied to certain higher-dimensional versions of transportation polytopes and there it produces more satisfying results: asymptotically, volumes of such polytopes turn out to be given by the Gaussian formula (2.1.1).

(4.2) Multi-index transportation polytopes

Let us fix an integer $\nu\geq 2$ and let us choose integers $k_{1},\ldots,k_{\nu}>1$. We consider the polytope of $P$ of $k_{1}\times\ldots\times k_{\nu}$ arrays of non-negative numbers $\xi_{j_{1}\ldots j_{\nu}}$, where $1\leq j_{i}\leq k_{i}$ for $i=1,\ldots,\nu$, with prescribed sums along the coordinate hyperplanes. Namely, we choose positive numbers $\beta_{ij}$, where $1\leq j\leq k_{i}$ for $i=1,\ldots,\nu$ and such that

for some $N$ and all $i=1,\ldots,\nu$ and define $P$ by the inequalities

Let us choose a pair of indices $1\leq i\leq\nu$ and $1\leq j\leq k_{i}-1$. We call the first sum in (4.2.1) the $j$-th sectional sum in direction $i$. Hence for each direction $i=1,\ldots,\nu$ we prescribe all but the last one sectional sum and also prescribe the total sum of the entries of the array. When $\nu=2$ we obtain the transportation polytope discussed in Section 4.1 We observe that every column $a$ of the matrix $A$ of the system (4.2.1) contains at most $\nu+1$ non-zero entries (necessarily equal to 1), so $\|a\|\leq\sqrt{\nu+1}$.

Let $z=\left(\zeta_{j_{1}\ldots j_{\nu}}\right)$ be the point maximizing

To bound the eigenvalues of $q$ from below, we consider a simpler quadratic form $\hat{q}$ which is the restriction of

Then $H_{i}$ is an eigenspace of $\hat{q}$ with the eigenvalue

for some real $\alpha_{1},\ldots,\alpha_{\nu};\omega$. Denoting

We observe that the restriction of $\hat{q}$ onto $L$ satisfies

for some $\delta=\delta(\nu)>0$ and all $\alpha_{1},\ldots,\alpha_{\nu}$ and $\omega$, we conclude that the eigenvalues of $\hat{q}$ exceed

where $\delta(\nu)>0$ is a constant depending on $\nu$ alone.

Suppose now that $\nu$ is fixed and let us consider a sequence of polytopes $P_{n}$ where $k_{1},\ldots,k_{\nu}$ grow roughly proportionately with $n$ and where the coordinates $\zeta_{j_{1}\ldots j_{\nu}}$ remain in the interval between two positive constants. Then the minimum eigenvalue of the quadratic form $q$ in Theorem 2.2 grows as $\Omega\left(n^{\nu-2}\right)$. In particular, for $\nu\geq 5$ Theorem 2.2 implies that the Gaussian formula (2.1.1) approximates the volume of $P_{n}$ with a relative error which approaches 0 as $n$ grows.

As an example, let us consider the (dilated) polytope $P_{k}$ of polystochastic tensors, that is $k\times\ldots\times k$ arrays of non-negative numbers with all sums along coordinate hyperplanes equal to $k^{\nu-1}$, cf. [Gr92]. By symmetry, we must have

Interestingly, for $\nu=2$, where our analysis is not applicable, the formula is smaller by a factor of $e^{1/3}$ than the true asymptotic value computed in [CM07b].

The number of multi-way contingency tables

We apply Theorems 2.4 and 2.6 to compute the number of multi-way contingency tables. The smallest eigenvalue of the quadratic form $q$ is bounded as in Section 4 and hence our main goal is to bound the additive error $\Delta$. Again, we begin our discussion with ordinary (two-way) contingency tables, where Theorems 2.4 and 2.6 do not guarantee the validity of the Gaussian approximation, but which provide a simple model case for computations used later in the case of multi-way tables.

Let us consider the transportation polytope $P=P(R,C)$, see Section 4.1, where the row sums $r_{1},\ldots,r_{m}$ and the column sums $c_{1},\ldots,c_{n}$ are integer. Integer points in $P(R,C)$ are called contingency tables and 0-1 points in $P(R,C)$ are called binary contingency tables with margins $R$ and $C$, see [DE85].

We assume that $P$ is defined by system (4.1.1). To estimate the additive error term $\Delta$ in Theorems 2.4 and 2.6, we need to construct sets of integer vectors of the following three types:

for $k=1,\ldots,m-1$ we construct a set $Y_{k}^{R}$ of $m\times n$ integer matrices $y$ such that the $k$-th row sum of $y$ is 1, all other row and column sums, with possible exceptions of the $m$-th row sum and $n$-th column sums are 0, and the total sum of the matrix entries is 0 as well; for $k=1,\ldots,n-1$ we construct a set $Y_{k}^{C}$ of $m\times n$ integer matrices $y$ such that the $k$-th column of $y$ sum is 1, all other row and column sums, with possible exceptions of the $m$-th row sum and the $n$-th column sums are 0, and the total sum of the matrix entries is 0 as well; we construct a set $Y_{0}$ of $m\times n$ integer matrices $y$ such that all the row and column sums of $y$ with possible exceptions of the $m$-th row sum and the $n$-th column sum are 0, and the total sum of the matrix entries is 1.

To construct $Y_{k}^{R}$, let us choose an integer $1\leq l\leq n$ and let us define a matrix $y=\left(\eta_{ij}\right)$ by letting $\eta_{kl}=1$, $\eta_{ml}=-1$ and letting all other entries $\eta_{ij}$ equal to 0. The set $Y_{k}^{R}$ contains $n$ vectors $y$ with pairwise disjoint support and hence the maximum eigenvalue $\rho_{k}^{R}$ of the corresponding quadratic form

is $2/n$. Similarly, to construct $Y_{k}^{C}$, let us choose an integer $1\leq l\leq m$ and let us define a matrix $y=\left(\eta_{ij}\right)$ by letting $\eta_{lk}=1$, $\eta_{ln}=-1$ and letting all other entries $\eta_{ij}$ equal to 0. The maximum eigenvalue $\rho_{k}^{C}$ of the corresponding quadratic form

Finally, to construct $Y_{0}$, let us choose two indices $1\leq k\leq m-1$ and $1\leq l\leq n-1$ and let us define a matrix $y=\left(\eta_{ij}\right)$ by letting $\eta_{kl}=-1$, $\eta_{kn}=1$, $\eta_{ml}=1$ and letting all other entries $\eta_{ij}$ equal to 0. For the corresponding quadratic form $\psi_{0}$ we have

in Theorems 2.4 and 2.6, so the additive term $\Delta$ is exponentially small in $\min\{m,n\}$. This bound is pretty weak but it is getting better as we pass to multiway tables. In fact, as Canfield and McKay have shown [CM07a], in the simplest case of $R=\left(r,\ldots,r\right)$ and $C=\left(c,\ldots,c\right)$, the number of contingency tables is not given by the Gaussian formula, since there is a 4-th order term correction.

(5.2) Multi-way contingency tables

Let us consider the $\nu$-index transportation polytope $P$ of Section 4.2. We assume that the affine span of $P$ is defined by system (4.2.1), where numbers $\beta_{ij}$ are all integer. The integer points in $P$ are called sometimes multi-way contingency tables while 0-1 points are called binary multi-way contingency tables, see [Go63] and [DL05].

To bound the additive error term $\Delta$ in Theorems 2.4 and 2.6, we construct a set $Y_{ij}$ of $k_{1}\times\ldots\times k_{\nu}$ arrays $y$ of integers such that the total sum of entries of $y$ is 0, the $j$-th sectional sum in the $i$-th direction is 1 all other sectional sums are 0, where by “all other” we mean all but the $k_{i}$-th sectional sums in every direction $i=1,\ldots,\nu$. For that, let us choose $\nu-1$ integers $m_{1},\ldots,m_{i-1},m_{i+1},\ldots,m_{\nu}$, where

and define $y=\left(\eta_{j_{1}\ldots j_{\nu}}\right)$ by letting

and letting all other coordinates of $y$ equal to 0.

Thus the set $Y_{ij}$ contains $k_{1}\cdots k_{i-1}k_{i+1}\cdots k_{\nu}$ elements $y$, and the corresponding quadratic form $\psi_{ij}$ can be written as

from which the maximum eigenvalue $\rho_{ij}$ of $\psi_{ij}$ is $2/k_{1}\cdots k_{i-1}k_{i+1}\cdots k_{\nu}$.

Next, we construct a set $Y_{0}$ of arrays $y$ of $k_{1}\cdots k_{\nu}$ integers $\left(\eta_{j_{1}\ldots j_{\nu}}\right)$ such that the total sum of entries of $y$ is $1$ while all sectional sums with a possible exception of the $k_{i}$-th sectional sum in every direction $i$ are equal 0. For that, let us choose $\nu$ integers $m_{1},\ldots,m_{\nu}$, where

and define $y=\left(\eta_{j_{1},\ldots,j_{\nu}}\right)$ by letting

and by letting all other coordinates equal to 0.

The set $Y_{0}$ contains $\left(k_{1}-1\right)\cdots\left(k_{\nu}-1\right)$ elements and the corresponding quadratic form $\psi_{0}$ of Theorems 2.4 and 2.6 can be written as

Therefore, the maximum eigenvalue $\rho_{0}$ of $\psi_{0}$ does not exceed

and the same bound can be used for the value of $\rho$ in Theorems 2.4 and 2.6.

Suppose now that $\nu$ is fixed and let us consider a sequence of polytopes $P_{n}$ where $k_{1},\ldots,k_{\nu}$ grow roughly proportionately with $n$. Then in Theorems 2.4 and 2.6 we have

Let us apply Theorem 2.6 for counting multi-way binary contingency tables. We assume, additionally, that for the point $z=\left(\zeta_{j_{1}\ldots j_{\nu}}\right)$ maximizing

on the transportation polytope $P_{n}$ we have

for some constant $1/2>\delta>0$ and all $j_{1},\ldots,j_{\nu}$. Then we can bound the additive term by

for some constant $\gamma>0$. On the other hand, by Hadamard’s inequality,

Therefore, for $\nu\geq 3$, the additive term $\Delta$ is negligible compared to the Gaussian term. From Section 4.2, we conclude that for $\nu\geq 5$ the relative error for the number of multi-way binary contingency tables in $P_{n}$ for the Gaussian approximation formula (2.5.1) approaches 0 as $n$ grows.

Similarly, we apply Theorem 2.4 for counting multi-way contingency tables. Here we assume, additionally, that for the point $z=\left(\zeta_{j_{1}\ldots j_{\nu}}\right)$ maximizing

on the transportation polytope $P_{n}$ the numbers $\zeta_{j_{1}\ldots j_{\nu}}$ lie between two positive constants. As in the case of binary tables, we conclude that for $\nu\geq 3$, the additive error term $\Delta$ is negligible compared to the Gaussian approximation term as $n\longrightarrow+\infty$. Therefore, for $\nu\geq 5$ the relative error for the number of multi-way contingency tables in $P_{n}$ for the Gaussian approximation formula (2.3.1) approaches 0 as $n$ grows.

Computations show that in the case of $k_{1}=\ldots=k_{\nu}=k$ for the matrix $A$ of constraints in Theorems 2.4 and 2.6 we have

Hence we obtain, for example, that the number of non-negative integer $\nu$-way $k\times\ldots\times k$ contingency tables with all sectional sums equal to $r=\alpha k^{\nu-1}$ is

provided $\nu\geq 5$, $k\longrightarrow+\infty$ and $\alpha$ stays between two positive constants. Interestingly, for $\nu=2$ (where our analysis is not applicable) the obtained number is off by a constant factor from the true asymptotic obtained in [CM07a].

Similarly, the number of binary $\nu$-way $k\times\ldots\times k$ binary contingency tables with all sectional sums equal to $r=\alpha k^{\nu-1}$ is

as long as $\nu\geq 5$, $k\longrightarrow+\infty$ and $\alpha$ remains separated from and $1$. Again, for $\nu=2$ the formula is off by a constant factor from the asymptotic obtained in [C+08].

Proof of Theorem 2.2

We start with some standard technical results.

The proof now follows by the inverse Fourier transform formula. ∎

We use the Laplace transform method. For every $1>\alpha>0$ we have

Optimizing on $\alpha$, we choose $\alpha=1-1/2\omega$ to conclude that

for the standard Gaussian random variable $y$. ∎

Scaling vectors $a_{j}$ if necessary, without loss of generality we may assume that $\theta=1$.

Hence our goal is to estimate the integral and, in particular, to compare it with

We estimate the integral separately over the three regions:

the outer region $\|t\|\geq 1/2$ the inner region $q(t)\leq\sigma$ the middle region $\|t\|<1/2$ and $q(t)>\sigma$.

We start with the outer region $\|t\|\geq 1/2$. Our goal is to show that the integral is negligible there.

The minimum value of the log-concave function

is attained at an extreme point of the polytope, that is, at a point where all but possibly one coordinate $\xi_{j}$ is either or $\|t\|^{2}$. Therefore,

By the Binet-Cauchy formula and the Hadamard bound,

It follows then that for a sufficiently large absolute constant $\gamma$ and the value of the integral over the outer region does not exceed $(\epsilon/10)(2\pi)^{d/2}\det(BB^{T})^{-1/2}$.

Next, we estimate the integral over the middle region with $\|t\|<1/2$ and $q(t)>\sigma$. Again, our goal is to show that the integral is negligible.

Therefore, by Part (1) of Lemma 6.2 we have

If $q(t)<\sigma$ then $\|t\|^{2}\leq\sigma/\lambda$ and hence

Thus for all sufficiently large $\gamma$, we have $|g(t)|\leq\epsilon/10$.

By Part (2) of Lemma 6.2, for all sufficiently large $\gamma$, we have

Proof of Theorem 2.6

First, we represent the number of 0-1 points as an integral.

Let $p_{j},q_{j}$ be positive numbers such that $p_{j}+q_{j}=1$ for $j=1,\ldots,n$ and let $\mu$ be the Bernoulli measure on the set $\{0,1\}^{n}$ of 0-1 vectors:

is the characteristic function of $Y=AX$ where $X$ is the multivariate Bernoulli random variable and $A$ is the matrix with the columns $a_{1},\ldots,a_{n}$.

The following result is crucial for bounding the additive error $\Delta$.

and let $\rho_{k}$ be the maximum eigenvalue of of $\psi_{k}$.

Suppose further that $0<\zeta_{1},\ldots,\zeta_{n}<1$ are numbers such that

Then for $t=\left(\tau_{1},\ldots,\tau_{d}\right)$ where $-\pi\leq\tau_{k}\leq\pi$ for $k=1,\ldots,d$ we have

if $\xi-\eta$ is an integer multiple of $2\pi$. Let

where $A^{\ast}$ is the transpose matrix of $A$. Since $|\tau_{k}|\leq\pi$, we have

where $\Pi$ is the parallelepiped consisting of the points $t=\left(\tau_{1},\ldots,\tau_{d}\right)$ with $-\pi\leq\tau_{k}\leq\pi$ for $k=1,\ldots,d$.

We split the integral (7.3.1) over three regions.

and as in the proof of Theorem 2.2 (see Section 6.4), we show that the integral over the region is asymptotically negligible for all sufficiently large $\gamma$.

If $q(t)<\sigma$ then $\|t\|_{\infty}\leq\|t\|\leq\sqrt{\sigma/\lambda}$ and

In particular, if constant $\gamma$ is large enough, we have $|g(t)|\leq\epsilon/10$.

By Part (2) of Lemma 6.2, for all sufficiently large $\gamma$, we have

and the proof is finished as in Section 6.4. ∎

Proof of Theorem 2.4

We begin with an integral representation for the number of integer points.

As in the proof of Lemma 7.1, the result follows from the multiple geometric expansion

is, of course, the characteristic function of $Y=AX$, where $X$ is the multivariate geometric random variable and $A$ is the matrix with the columns $a_{1},\ldots,a_{n}$.

The following result is an analogue of Lemma 7.2.

and let $\rho_{k}$ be the maximum eigenvalue of $\psi_{k}$. Suppose further that $\zeta_{1},\ldots,\zeta_{n}>0$ are numbers such that

Then for $t=\left(\tau_{1},\ldots,\tau_{d}\right)$ where $-\pi\leq\tau_{k}\leq\pi$ for $k=1,\ldots,d$, we have

Let us denote $\xi_{j}=\gamma_{j}^{2}$ for $j=1,\ldots,n$. The minimum of the log-concave function

on the polytope defined by the inequalities $0\leq\xi_{j}\leq\pi^{2}$ for $j=1,\ldots,n$ and

is attained at an extreme point of the polytope, where all but possibly one coordinate $\xi_{j}$ is either or $\pi^{2}$. The number of non-zero coordinates $\xi_{j}$ is at least $\tau_{k}^{2}/\rho_{k}\pi^{2}$ and the proof follows by (8.2.1). ∎

where $\Pi$ is the parallelepiped consisting of the points $t=\left(\tau_{1},\ldots,\tau_{d}\right)$ with $-\pi\leq\tau_{k}\leq\pi$ for $k=1,\ldots,d$.

Similarly to the proof of Theorem 2.6 (see Section 7.3), assuming that $\|t\|_{\infty}\leq 1/4\theta$, we write

and as in the proof of Theorem 2.6 (see Section 7.3), we split the integral (8.3.1) over the three regions:

the outer region: $\|t\|_{\infty}\geq 1/4\theta$, the middle region: $q(t)\geq\sigma$ and $\|t\|_{\infty}\leq 1/4\theta$ and the inner region: $q(t)<\sigma$.

in the middle region and we bound the integral there as in Section 7.3.

In the inner region, we have $\|t\|_{\infty}\leq\|t\|\leq\sqrt{\sigma/\lambda}$ and

The proof is finished as in Section 7.3. ∎