Asymptotic estimates for the number of contingency tables, integer flows, and volumes of transportation polytopes

Introduction and main results

Let $m>1$ and $n>1$ be integers and let $R=\left(r_{1},\ldots,r_{m}\right)$ and $C=\left(c_{1},\ldots,c_{n}\right)$ be positive integer vectors such that

We are interested in the number $\#(R,C)$ of $m\times n$ non-negative integer matrices, also known as contingency tables, with row sums $R$ and column sums $C$, called margins. Computing or estimating numbers $\#(R,C)$ has attracted a lot of attention, because of the relevance of these numbers in statistics, see [Goo76], [DE85], combinatorics, representation theory, and elsewhere, see [DG85], [DG04]. Of interest are asymptotic formulas, see [BBK72], [Ben74] and most recent [CM07a], [GM07], algorithms with rigorous estimates of the performance guarantees, see [DKM97], [Mor02], [CD03], [BLV04], and heuristic approaches which may lack formal justification but tend to work well in practice [Goo76], [DE85], [C+05].

Let $R=\left(r_{1},\ldots,r_{m}\right)$ and $C=\left(c_{1},\ldots,c_{n}\right)$ be positive integer vectors such that $r_{1}+\ldots+r_{m}=c_{1}+\ldots+c_{n}=N$. Let us define a function

on the open cube $0<x_{i},y_{j}<1$ and for the number $\#(R,C)$ of non-negative integer $m\times n$ matrices with row sums $R$ and column sums $C$ we have

where $\gamma>0$ is an absolute constant.

More precisely, the lower bound we prove is

provided $m+n\geq 10$. Recall that from Stirling’s formula

and hence the product in front of $\rho(R,C)$ indeed exceeds $N^{-\gamma(m+n)}$ for some absolute constant $\gamma>0$.

We note that the substitution $x_{i}=e^{-t_{i}}$ and $y_{j}=e^{-s_{j}}$ transforms the problem of computing $\rho$ into the problem of minimizing the convex function

on the positive orthant $s_{i},t_{j}>0$, so that methods of convex optimization can be applied to compute $\rho$ in time polynomial in $m+n$ and $\ln N$, see [NN94].

Theorem 1.1 estimates the number $\#(R,C)$ of contingency tables within an $N^{O(m+n)}$ factor. This estimate provides, asymptotically, the main term of $\log\#(R,C)$ for all but very sparse cases, where margins $r_{i}$ and $c_{j}$ are small compared to the sizes $m$ and $n$ of the matrix. For example, if the margins $r_{i}$ and $c_{j}$ are at least linear in $m$ and $n$ then $\#(R,C)$ is at least as big as $\gamma^{mn}$ for some constant $\gamma>1$. By now, the sparse case of small $r_{i}$ and $c_{j}$ is well understood, thanks especially to the recent paper [GM07]. The case of moderate to high margins seems to be the most difficult. To the author’s knowledge, the estimate of Theorem 1.1 is the only rigorously proven effective estimate of $\#(R,C)$ for generic $R$ and $C$ (if all $r_{i}$’s are equal and all $c_{j}$’s are equal, recent paper [CM07a] provides a precise asymptotic formula for the number of tables). Theorem 1.1 allows us to find faults with the very intuitive “independence heuristic” for counting contingency tables and points out at some strange “attraction” phenomena in the space of matrices. Quite counter-intuitively, we conclude that in the uniform probability space of the $m\times n$ non-negative integer matrices with the total sum of entries equal to $N$, the event consisting of the matrices with row sums $R$ and the event consisting of the matrices with column sums $C$ attract exponentially in $mn$ provided the vectors $R$ and $C$ are sufficiently far from constant vectors, see Section 2 for the precise statements and details.

Let $R=\left(r_{1},\ldots,r_{m}\right)$ and $C=\left(c_{1},\ldots,c_{n}\right)$ be positive integer vectors such that $r_{1}+\ldots+r_{m}=c_{1}+\ldots+c_{n}=N$ and let $\Cal{P}=\Cal{P}(R,C)$ be the polytope of non-negative $m\times n$ matrices with row sums $r_{1},\ldots,r_{m}$ and column sums $c_{1},\ldots,c_{n}$.

be the maximum value of the product of entries of a matrix from $\Cal{P}$. Then for the volume of $\Cal{P}$ we have

where $\gamma>0$ is an absolute constant.

follow. When the margins are scaled, $(R,C)\longmapsto(tR,tC)$ for $t>0$, the volume of $\Cal{P}$ and both the upper and the lower bounds get multiplied by $t^{\dim\Cal{P}}$.

Computing $\beta$ reduces to finding the maximum of the concave function

on the transportation polytope $\Cal{P}$ and hence can be done efficiently (in time polynomial in $m+n$ and $\ln N$) by existing methods [NN94].

Computing or estimating volumes of transportation polytopes has attracted considerable attention as a testing ground for methods of convex geometry [Sch92], combinatorics [Pak00], analysis and algebra [BLV04], [BP03], [DLY03]. In a recent breakthrough [CM07b], Canfield and McKay obtained a precise asymptotic expression for the volume of the Birkhoff polytope (when $r_{i}=c_{j}=1$ for all $i$ and $j$) and in the more general case of all the row sums being equal and all the column sums being equal. If $R=C=\left(1,\ldots,1\right)$, the formula of [CM07b] gives

whereas the formula of Theorem 1.2 implies that, ignoring lower-order terms, we have

in that case (since by symmetry the maximum $\beta$ of the product of coordinates $x_{ij}$ is attained at $x_{ij}=1/n$). Theorem 1.2 seems to be the only rigorously proven estimate of the volume of the transportation polytope available for general margins.

We note that from the purely algorithmic perspective, volumes of polytopes and convex bodies can be computed in randomized polynomial time, see [Bol97] for a survey.

Theorem 1.1 can be extended to counting with weights.

Let us fix a non-negative matrix $W=\left(w_{ij}\right)$, which we call the matrix of weights. We consider the following expression

We prove the following extension of Theorem 1.1.

Let $R=\left(r_{1},\ldots,r_{m}\right)$ and $C=\left(c_{1},\ldots,c_{n}\right)$ be positive integer vectors such that $r_{1}+\ldots+r_{m}=c_{1}+\ldots+c_{n}=N$ and let $W=\left(w_{ij}\right)$ be an $m\times n$ non-negative matrix of weights. Let us define a function

Then, for the number $T(R,C;W)$ of weighted non-negative integer matrices with row sums $r_{1},\ldots,r_{m}$ and column sums $c_{1},\ldots,c_{n}$, we have

where $\gamma>0$ is an absolute constant.

More precisely, the lower bound we prove is

As in Theorem 1.1, substituting $x_{i}=e^{-t_{i}}$ for $i=1,\ldots,m$ and $y_{j}=e^{-s_{j}}$ for $j=1,\ldots,n$ we reduce the problem of computing $\rho$ to the problem of finding the infimum of the convex function

Again, the value of $\rho$ can be computed efficiently, both in theory and in practice, by methods of convex optimization, cf. [NN94].

For positive matrices $W=\left(w_{ij}\right)$ the infimum $\rho(R,C;W)$ in Theorem 1.3 is attained at a particular point and there is a convenient dual description of $\rho(R,C;W)$.

Let $\Cal{P}=\Cal{P}(R,C)$ be the transportation polytope of the $m\times n$ non-negative matrices $X=\left(x_{ij}\right)$ with row sums $R$ and column sums $C$ and let us fix an $m\times n$ positive matrix $W=\left(w_{ij}\right)$ of weights, so $w_{ij}>0$ for all $i,j$. For an $m\times n$ non-negative matrix $X=\left(x_{ij}\right)$ let us define

Then $g(X;W)$ is a strictly concave function of $X$ and attains its maximum on $\Cal{P}$ at a unique positive matrix $Z=Z(R,C;W)$. One can write $Z=\left(z_{ij}\right)$ in the form

In particular, if $w_{ij}=1$ for all $i,j$, then

In Section 2, we consider consequences of Theorems 1.1 and 1.2 for the “independence heuristic”. The heuristic was, apparently, first discussed by Good, see [Goo76]. It asserts that if we consider the space of non-negative integer $m\times n$ matrices with the total sum $N$ of entries as a probability space with the uniform measure then the event consisting of the matrices with the row sums $r_{1},\ldots,r_{m}$ is “almost independent” from the event consisting of the matrices with the column sums $c_{1},\ldots,c_{n}$. We show that if the row sums $r_{i}$ and the column sums $c_{j}$ are sufficiently generic then the independence heuristic tends to underestimate the number of tables as badly as within a factor of $\gamma^{mn}$ for some absolute constant $\gamma>1$. We see that in fact (rather counter-intuitively), instead of independence, we have attraction (positive correlation) of the events.

In Section 3, we state a general result (Theorem 3.1), which provides a reasonably accurate estimate for the volume of the section of the standard simplex by a subspace of a small codimension. Theorem 3.1 states that in a sufficiently generic situation the volume of the section is determined by the maximum value of the product of the coordinates of a point in the section. This estimate immediately implies Theorem 1.2 and is one of the two crucial ingredients in the proofs of Theorems 1.1 and 1.3. Theorem 3.1 appears to be new and may be interesting in its own right.

In Section 4, we state some preliminaries from convex geometry needed to prove Theorem 3.1.

In Section 5, we prove Theorems 3.1 and 1.2.

In Section 6, we describe the second main ingredient for the proofs of Theorems 1.1 and 1.3, the integral representation from [Ba07] and [Ba08] for the number $\#(R,C)$ of tables and the number $T(R,C;W)$ of weighted tables.

In Section 7, we prove Theorems 1.1 and 1.3 and Lemma 1.4.

In what follows, we use $\gamma$ to denote a positive constant.

The independence heuristic and the exponential attraction in the space of matrices

The following heuristic approach to counting contingency tables was suggested by Good [Goo76]. Let us consider the space of all $m\times n$ non-negative integer matrices with the total sum of entries $N$ as a probability space with the uniform measure. Then the probability that a matrix from this space has row sums $R=\left(r_{1},\ldots,r_{m}\right)$ is exactly

Similarly, the probability that a matrix has column sums $C=\left(c_{1},\ldots,c_{n}\right)$ is exactly

Assuming that the two events are almost independent, one estimates the number $\#(R,C)$ of contingency tables by the independence heuristic $I(R,C)$:

For example, if $m=n=4$, $R=(220,215,93,64)$, $C=(108,286,71,127)$ with $N=592$ then

Given margins $R=\left(r_{1},\ldots,r_{n}\right)$ and $C=\left(c_{1},\ldots,c_{m}\right)$ such that not all row sums $r_{i}$ are equal and not all column sums $c_{j}$ are equal, we will construct a sequence of margins $(R_{k},C_{k})$, where $R_{k}$ is a $km$-vector and $C_{k}$ is a $kn$-vector such that the ratio $\#(R_{k},C_{k})/I(R_{k},C_{k})$ grows as $\gamma^{k^{2}}$ for some $\gamma=\gamma(R,C)>1$.

(2.2) Cloning margins

Let us choose some margins $R=\left(r_{1},\ldots,r_{m}\right)$ and $C=\left(c_{1},\ldots,c_{n}\right)$ such that $r_{1}+\ldots+r_{m}=c_{1}+\ldots+c_{n}=N$. For a positive integer $k$, let us consider the new “clone” margins

In other words, we obtain margins $(R_{k},C_{k})$ if we choose an arbitrary matrix $X$ with row sums $R$ and column sums $C$, consider the $km\times kn$ block matrix $Y_{k}$ consisting of $k^{2}$ blocks $X$ and let $R_{k}$ be the row sums of $Y_{k}$ and let $C_{k}$ be the column sums of $Y_{k}$. Hence we consider $km\times kn$ matrices with the total sum of the matrix entries equal to $k^{2}N$.

Let us introduce the multivariate entropy function

where $p_{1},\ldots,p_{d}$ are non-negative numbers such that $p_{1}+\ldots+p_{d}=1$. Using the standard asymptotic estimate for binomial coefficients (available, for example, via Stirling’s formula)

(2.3) The exponential attraction in the space of matrices

Let us choose margins $R=\left(r_{1},\ldots,r_{m}\right)$ and $C=\left(c_{1},\ldots,c_{n}\right)$ such that not all row sums $r_{i}$ are equal and not all column sums $c_{j}$ are equal. Our goal is to show that

so the ratio $\#(R_{k},C_{k})/I(R_{k},C_{k})$ grows as $\gamma^{k^{2}}$ for some $\gamma=\gamma(R,C)>1$, as we clone margins $(R,C)\longmapsto(R_{k},C_{k})$.

where $Y=\left(y_{ij}\right)$ is the independence matrix with $y_{ij}=r_{i}c_{j}/N$ for all $i,j$ and

On the other hand, it is easy to check that

Let us consider the $m\times n$ matrix with the $(i,j)$-th entry equal to

$(r_{i}c_{j}+N)/(N^{2}+Nmn)$. The $i$-th row sum of the matrix is $(r_{i}+n)/(N+mn)$, the $j$-th column sum is $(c_{j}+m)/(N+mn)$ while the sum of all the entries of the matrix is 1. Using the inequality relating the entropies of two partitions of a probability space with the entropy of the intersection of the partition (see, for example, [Khi57]), we conclude that

Identities (2.3.5) are equivalent to $(N-r_{i}m)(N-c_{j}n)=0$, which, in turn, equivalent to all row sums being equal $r_{i}=N/m$ or all column sums being equal $c_{j}=N/n$.

Summarizing (2.2.1), (2.2.2), (2.3.2), and (2.3.3) we conclude that inequality (2.3.1) indeed holds if not all row sums $r_{i}$ are equal and not all column sums $c_{j}$ are equal. Therefore, in the space of $km\times kn$ matrices with the sum $k^{2}N$ of all entries the two events

instead of being asymptotically independent, attract exponentially in $k^{2}$, that is,

for some $\gamma=\gamma(R,C)>1$ and all sufficiently large $k$.

Starting with non-constant margins $(R,C)$ the cloning procedure $(R,C)\longmapsto(R_{k},C_{k})$ produces margins which stay away from from constant and maintain the density $N/mn$ separated from 0. Similar analysis shows that the phenomenon of attraction of the events $\Cal{R}_{k}$ and $\Cal{C}_{k}$ defined by (2.3.6) holds for more general sequences of margins $(R_{k},C_{k})$ of growing dimensions which stay sufficiently away from uniform and sparse.

Two terms contribute to the difference $\ln\#(R,C)-\ln I(R,C)$:

first, the difference $g(Z)-g(Y)$, where $Z$ is the matrix of Lemma 1.4 at which the maximum of the function $g(X)=\sum_{ij}(x_{ij}+1)\ln(x_{ij}+1)-x_{ij}\ln x_{ij}$ on the transportation polytope $\Cal{P}(R,C)$ is attained and $Y=\left(y_{ij}\right)$ is the independence matrix $y_{ij}=r_{i}c_{j}/N$, cf. (2.3.2);

and second, the difference (multiplied by $(N+mn)$) between the entropies on the right hand side of (2.3.4) and the left hand side of (2.3.4).

As long as either of these differences remains large enough to overcome the error term of O\bigl{(}(m+n)\ln N\bigr{)} coming from Theorem 1.1, we have the asymptotic positive correlation of sequences of events $\Cal{R}_{k}$ and $\Cal{C}_{k}$ in (2.3.6).

On the other hand, the independence estimate $I(R,C)$ produces a reasonable approximation to $\#(R,C)$ in the cases of sparse tables (cf. [GM07]) and tables with constant margins (cf. [CM07a]). One can show that if all row sums are equal or if all column sums are equal then indeed

where $(R_{k},C_{k})$ are cloned margins $(R,C)$. Indeed, if all $r_{i}$ are equal then the symmetry argument shows that the matrix $Z=\left(z_{ij}\right)$ in Lemma 1.4 satisfies $z_{ij}=c_{j}/m$ for all $i$ and $j$, and, similarly, if all $c_{j}$ are equal then we have $z_{ij}=r_{i}/n$ for all $i,j$. In either case we have $Z=Y$ in (2.3.2) and, as we have already discussed, equations (2.3.5) hold as well.

The volume of a section of a simplex

and let $\Delta\subset\Cal{A}$ be the standard $(d-1)$-dimensional open simplex defined by the inequalities

Let $L\subset\Cal{A}$ be an affine subspace intersecting $\Delta$. Suppose that $\dim L=d-k-1$, so the the codimension of $L$ in $\Cal{A}$ is $k\geq 1$. Our aim is to estimate the volume of the intersection $\operatorname{vol}_{d-k-1}(L\cap\Delta)$ within a reasonable accuracy when the codimension $k$ of $L$ is small. It turns out that the volume is controlled by one particular quantity, namely the maximum value of the product of the coordinates of a point $x\in\Delta\cap L$.

Let $L\subset\Cal{A}$ be an affine subspace intersecting $\Delta$ and such that $\dim L=d-k-1$ where $k\geq 1$. Suppose that the maximum of the function

on $\Delta\cap L$ is attained at $a=\left(\alpha_{1},\ldots,\alpha_{d}\right)$.

We are interested in the situation of $k\sim\sqrt{d}$, so ignoring lower-order terms in the logarithmic order, we get

provided the maximum value of the product of the coordinates of a point $x\in\Delta\cap L$ is attained at $a=\left(\alpha_{1},\ldots,\alpha_{d}\right)$ and all $\alpha_{i}$ are not too small.

We deduce Theorem 3.1 from the following result.

Let $H\subset\Cal{A}$ be an affine hyperplane in $\Cal{A}$ intersecting $\Delta$. If $H$ does not pass through the center $c$ of $\Delta$, let $H^{-}\subset\Cal{A}$ be the open halfspace bounded by $H$ that does not contain $c$ and if $H$ passes through $c$ let $H^{-}\subset\Cal{A}$ be either of the open halfspaces bounded by $H$.

attains its maximum on $\Delta\cap H$ at a point $a=\left(\alpha_{1},\ldots,\alpha_{d}\right)$.

Then, for some absolute constant $\gamma>0$ we have

We can choose $\gamma=1/2e^{3}\approx 0.025$.

Preliminaries from convex geometry

Let $H\subset\Cal{A}$ be an affine hyperplane in $\Cal{A}$ passing through the center $c$ of $\Delta$.

Part (1) is a particular case of a more general result of Grünbaum [Grü60] on hyperplane sections through the centroid of a convex body. In fact, in dimension $d$ one can choose

As K. Ball and M. Fradelizi explained to the author, a stronger estimate than that of Part (2) can be obtained by combining techniques of [Bal88] and [Frad97]. Nevertheless, we present a proof of Part (2) below since the same approach is used later in the proof of Theorem 3.1.

To prove Part (2), let $H^{\bot}\subset\Cal{A}$ be a line orthogonal to $H$. Let us consider the orthogonal projection $pr:\Cal{A}\longrightarrow H^{\bot}$ and let $Q=pr(\Delta)$ be the image of the simplex. Since $\Delta$ is contained in a ball of radius 1, $Q$ is an interval of length at most 2.

be the volume of the inverse image of $y$. By the Brunn-Minkowski inequality, the function $\nu$ is log-concave, see [Bal88], [Bal97].

Our goal is to bound $\nu(y_{0})$ from below. The point $y_{0}$ splits the interval $Q$ into two subintervals, $Q^{+}=pr(\Delta\cap H^{+})$ and $Q^{-}=pr(\Delta\cap H^{-})$ of length at most 2 each.

Using Part (1) we conclude that there exist $y^{+}\in Q^{+}$ and $y^{-}\in Q^{-}$ such that

Since $y_{0}$ is a convex combination of $y^{+}$ and $y^{-}$, by the log-concavity of $\nu$ we must have

Let us choose a point $a=\left(\alpha_{1},\ldots,\alpha_{d}\right)$ in $\Delta$, and let us consider the projective transformation $T_{a}:\Delta\longrightarrow\Delta$

The inverse transformation is $T_{b}$ for $b=\left(\alpha_{1}^{-1},\ldots,\alpha_{d}^{-1}\right)$. Clearly,

where $c$ is the center of $\Delta$. For $x\in\Delta$, the derivative $DT_{a}(x)$ is a linear transformation

Our immediate goal is to compute the Jacobian $|DT_{a}(x)|$ at $x\in\Delta$.

Let us choose a point $a=\left(\alpha_{1},\ldots,\alpha_{d}\right)$ in the simplex $\Delta$ and let us consider the projective transformation

for $x=(x_{1},\ldots,x_{d})$ and $y=(y_{1},\ldots,y_{d})$.

Let $DT_{a}(x):\Cal{H}\longrightarrow\Cal{H}$ be the derivative of $T_{a}$ at $x\in\Delta$ and $|DT_{a}(x)|$ the corresponding value of the Jacobian. Then

while the $(i,j)$-th entry for $i\neq j$ is

let $B$ be the diagonal matrix with the diagonal entries $\alpha_{1},\ldots,\alpha_{d}$, and let $C$ be the matrix with the $(i,j)$th entry equal to $\alpha_{i}\alpha_{j}x_{i}$ for all $1\leq i,j\leq d$. Then we can write

Let $B_{i}$ and $C_{i}$ be the $(d-1)\times(d-1)$ matrices obtained from $B$ and $C$ respectively by crossing out the $i$th row and column.

where $I$ is the $(d-1)\times(d-1)$ identity matrix. Now $B_{i}^{-1}C_{i}$ is a matrix of rank 1 with the non-zero eigenvalue equal to the trace of $B_{i}^{-1}C_{i}$, which is

Therefore, the sum of the $d$ of $(d-1)\times(d-1)$ principle minors of $B-\beta C$ is

and the sum of the $(d-1)\times(d-1)$ principle minors of $DT_{a}(x)=\beta(B-\beta C)$ is

Next, we will need a technical estimate, which shows that if the volume of the section of the simplex by an affine subspace of a small codimension is sufficiently large and if the subspace cuts sufficiently deep into the simplex then a neighborhood of the section in the simplex has a sufficiently large volume.

Let $L\subset\Cal{A}$ be an affine subspace, $\dim L=d-k-1$. Suppose that there is a point $a\in L\cap\Delta$, $a=\left(\alpha_{1},\ldots,\alpha_{d}\right)$ such that

and let us define a neighborhood $Q$ of $\Delta\cap L$ by

Then, for any affine hyperplane $H\subset\Cal{A}$ passing through $L$ we have

where $H^{+}$ and $H^{-}$ are the halfspaces bounded by $H$ and $\gamma>0$ is an absolute constant. One can choose $\gamma=1/2e\approx 0.18$.

Since $Q_{0}$ is the contraction of $\Delta\cap L$ we have

Moreover, for any $x\in Q_{0}$, $x=\left(x_{1},\ldots,x_{d}\right)$, we have

For every point $x\in Q_{0}$ let us consider the cube

Then $\left(I_{x}\cap\Cal{A}\right)\subset\Delta$. The intersection of $I_{x}$ with the $k$-dimensional affine subspace $L^{\bot}_{x}\subset\Cal{A}$ orthogonal to $L$ and passing through $x$ is centrally symmetric with respect to $x$ and, by Vaaler’s Theorem [Vaa79], satisfies

Proofs of Theorems 1.2, 3.1, and 3.2

If $c\in H$ the result follows by Lemma 4.1. Hence we assume that $c\notin H$.

The hyperplane $H$ is orthogonal to the gradient of $f(x)$ at $x=a$ and passes through $a$, from which it follows that $H$ can be defined in $\Cal{A}$ by the equation

while the halfspace $H^{-}$ is defined by the inequality

Let us consider the projective transformation $T_{a}:\Delta\longrightarrow\Delta$ defined by the formula of Lemma 4.2. Hence $T_{a}(c)=a$. Moreover, the inverse image $T^{-1}_{a}(H)$ is the hyperplane $H_{0}$ defined in $\Cal{A}$ by the equation

and the inverse image $T^{-1}_{a}\left(\Delta\cap H^{-}\right)$ is the intersection $\Delta\cap H_{0}^{-}$, where $H_{0}^{-}$ is the halfspace defined by the inequality

Let us prove the lower bound. By Part (2) of Lemma 4.1,

We recall that $H_{0}$ passes through the center of the simplex and apply Lemma 4.3 with $\epsilon=1$. Namely, we define

(5.2) Proof of Theorem 3.1

The proof of Part (1) is similar to that of Part (2) of Lemma 4.1. Let $L^{\bot}\subset\Cal{A}$ be a $k$-dimensional subspace orthogonal to $L$ in $\Cal{A}$ and let

be the orthogonal projection. Let $Q\subset L^{\bot}$, $Q=pr(\Delta)$, be the image of the simplex. Clearly, $Q$ lies in a ball of radius $1$, so

be the volume of the inverse image of $y$. By the Brunn-Minkowski inequality, the function $\nu$ is log-concave, so for every $\alpha>0$ the set

is convex. Moreover, for all Borel sets $Y\subset Q$ we have

We conclude that there exist points $y^{+}\in H^{+}$ and $y^{-}\in H^{-}$ such that

In other words, for any affine hyperplane $H\subset L^{\bot}$ through $y_{0}$ on either side of the hyperplane there are points $y^{+},y^{-}$ for which inequality (5.2.1) holds. Hence $y_{0}$ lies in the convex hull of points $y$ for which the inequality holds. The proof of Part (1) follows by the log-concavity of $\nu$.

Let us prove Part (2). Since $a$ is the maximum point of the strictly concave function

on $\Delta\cap L$, the gradient of $f$ at $a$ is orthogonal to $L$. Hence $L$ is orthogonal to the vector

If $a\neq c$, let $H\subset\Cal{A}$ be the affine hyperplane defined by the equation

and if $a=c$ let $H$ be any affine hyperplane containing $L$. In either case $L\subset H$ and the maximum values of $f$ on $\Delta\cap H$ and on $\Delta\cap L$ coincide and are equal to $f(a)$. Therefore, by Theorem 3.2, we have

for some open halfspace $H^{-}$ bounded by $H$.

(5.3) Proof of Theorem 1.2

Let us consider the contracted polytope $N^{-1}\Cal{P}$ defined by the equations

Then $N^{-1}\Cal{P}$ can be represented as an intersection of the standard simplex in the space of $m\times n$ matrices and an affine subspace of dimension $(m-1)(n-1)$. We are going to use Theorem 3.1. Let $A=\left(\alpha_{ij}\right)$, $A\in N^{-1}\Cal{P}$, be the point maximizing the product of the coordinates. Writing the optimality condition for

and some $\lambda_{1},\ldots\lambda_{m}$ and $\mu_{1},\ldots,\mu_{n}$. Since $\lambda_{i}+\mu_{j}>0$ for all $i,j$, we may assume that $\lambda_{i},\mu_{j}>0$ for all $i,j$. If $\lambda_{i}>nN/r_{i}$ for some $i$ then $\alpha_{ij}<r_{i}/nN$ for all $j$, which is a contradiction. If $\mu_{j}>mN/c_{j}$ for some $j$ then $\alpha_{ij}<c_{j}/mN$ for all $i$ which is a contradiction. Hence $\lambda_{i}\leq nN/r_{i}$ for $i=1,\ldots,m$ and $\mu_{j}\leq mN/c_{j}$ for $j=1,\ldots,n$, from which

The proof now follows by Theorem 3.1 with $d=mn$, $k=m+n-2$, and

An integral representation for the number of contingency tables

In this section, we recall bounds for $\#(R,C)$ obtained in [Ba07] and [Ba08].

Our estimates for the number $\#(R,C)$ of contingency tables essentially use the theory of matrix scaling, see [Si64], [MO68], [RS89]. Let us fix non-negative vectors $R=\left(r_{1},\ldots,r_{m}\right)$, $C=\left(c_{1},\ldots,c_{n}\right)$, such that

Then for every $m\times n$ positive matrix $X=\left(x_{ij}\right)$ there exist a positive $m\times n$ matrix $L=\left(l_{ij}\right)$ and positive numbers $\lambda_{1},\ldots,\lambda_{m}$ and $\mu_{1},\ldots,\mu_{n}$ such that

Moreover, given $X$, the matrix $L$ is unique while the numbers $\lambda_{i}$ and $\mu_{j}$ are unique up to a re-scaling:

(6.2) Function ϕitalic-ϕ\phi

where $\lambda_{i}$ and $\mu_{j}$ are numbers such that equations (6.1.1) hold, on positive $m\times n$ matrices $X$. It turns out that $\phi$ is continuous (it is also log-concave but we don’t use that), positive homogeneous of degree $N$,

for $\alpha>0$ and positive matrix $X$, and monotone

provided $X$ and $Y$ are positive matrices satisfying $x_{ij}\geq y_{ij}$ for all $i,j$, see, for example, [Ba07] and [Ba08].

Alternatively, $\phi(X)$ can be defined by

where the minimum is taken over all positive $m$-vectors $a=\left(\alpha_{1},\ldots,\alpha_{m}\right)$ and positive $n$-vectors $b=\left(\beta_{1},\ldots,\beta_{n}\right)$ satisfying

(6.3) The bounds

and let $\Delta\subset\Cal{A}$ be the standard open simplex defined by the inequalities

Therefore, we have an approximation within up to an $N^{\gamma(m+n)}$ factor for some absolute constant $\gamma>0$:

In fact, we will be using only a lower bound in (6.3.1).

For completeness, let us sketch the main ingredients of the proof of (6.3.1).

Recall that the permanent of an $N\times N$ matrix $A=\left(a_{ij}\right)$ is defined by the formula

where the sum is taken over all $N!$ permutations $\sigma$ from the symmetric group $S_{N}$. For an $m\times n$ matrix $X=\left(x_{ij}\right)$ let us define the $N\times N$ block matrix $A(X)$ that has $mn$ blocks of sizes $r_{i}\times c_{j}$ for $i=1,\ldots,m$ and $j=1,\ldots,n$ with the $(i,j)$-th block filled by the copies of $x_{ij}$. A combinatorial computation produces the following expansion

where the sum is taken over all $m\times n$ non-negative integer matrices $D=\left(d_{ij}\right)$ with row sums $R$ and column sums $C$. From this expansion we obtain the formula

cf. Lemma 4.1 of [Ba08]. Given a matrix $X\in\Delta$, let $\lambda_{1},\ldots,\lambda_{m}$ and $\mu_{1},\ldots,\mu_{n}$ be its scaling factors so that (6.1.1) holds. Let $B(X)$ be the matrix obtained by dividing the entries in the $(i,j)$-th block of $A(X)$ by $\lambda_{i}r_{i}\mu_{j}c_{j}$, so the entries in the $(i,j)$-th block of $B(X)$ are equal to $l_{ij}/r_{i}c_{j}$. Hence

cf. Section 3.1 of [Ba08]. Now we notice that $B(X)$ is a doubly stochastic matrix, that is, a non-negative matrix with row and column sums equal to 1. The classical estimate for permanents of doubly stochastic matrices conjectured by van der Waerden and proved by Falikman and Egorychev (see [Fa81], [Eg81], and Chapter 12 of [LW01]) asserts that

and hence the lower bound in (6.3.1) follows. The upper bound in (6.3.1) follows from the inequality for permanents conjectured by Minc and proven by Bregman, (see [Br73] and Chapter 11 of [LW01]), which results in

since the entries in the $(i,j)$-th block of $B(X)$ do not exceed $\min\{1/r_{i},\ 1/c_{j}\}$, see Section 5 of [Ba08] for details.

(6.4) Slicing the simplex

The crucial observation which makes the integral

amenable to analysis is that the simplex $\Delta$ can be sliced by affine subspaces of codimension $m+n-1$ into sections on which function $\phi$ remains constant.

(6.5) Modification for weighted tables

Similar identities an inequalities hold for weighted tables. For a positive matrix $W=\left(w_{ij}\right)$ of weights, we define the function

and $\phi_{R,C}$ is the unweighted function defined in Section 6.2. Then

see [Ba07], [Ba08], and the proof sketch in Section 6.3.

Proofs of Theorems 1.1 and 1.3 and Lemma 1.4

It is straightforward to check that the function

is strictly concave for $x>0$. Therefore, the maximum of $g(X;W)$ on $\Cal{P}(R,C)$ is attained at a single point $Z=\left(z_{ij}\right)$. Let us show that necessarily $z_{ij}>0$ for all $i,j$.

the derivative of $g(x;w)$ at $x>0$ is finite and the right derivative at $x=0$ is $+\infty$. Let $Y\in\Cal{P}(R,C)$ be a matrix with positive entries, for example, $Y=\left(y_{ij}\right)$ where $y_{ij}=r_{i}c_{j}/N$. If $z_{ij}=0$ for some $i,j$ then

for some sufficiently small $\epsilon>0$, which is a contradiction.

Thus $z_{ij}>0$ for all $i,j$ and hence $Z$ lies in the relative interior of $\Cal{P}(R,C)$. Therefore the gradient of $g(X;W)$ at $X=Z$ is orthogonal to the affine span of $\Cal{P}(R,C)$, that is,

and some $\lambda_{1},\ldots,\lambda_{m}$, $\mu_{1},\ldots,\mu_{n}$.

is attained in the region $x_{1},\ldots,x_{m}>0$, $y_{1},\ldots,y_{n}>0$, and $w_{ij}x_{i}y_{j}<1$ for all $i,j$.

Using (7.1.1) and (7.1.2), we conclude that

We start with a technical lemma, which is a straightforward modification of Lemma 4.3.

Let $L\subset\Cal{A}$ be an affine subspace, $\dim L=d-k-1$ for $k\geq 1$. Suppose that there is a point $A=\left(\alpha_{ij}\right)$, $A\in\Delta\cap L$, such that

Suppose further that the value of the function $\phi=\phi_{R,C;W}$ on $\Delta\cap L$ is constant and equal to $\tau$. Then

for some absolute constant $\gamma>0$ (one can choose $\gamma=e^{-2}\approx 0.14$).

and for any $X\in Q_{0}$, $X=\left(x_{ij}\right)$, we have

We note that for every $X\in Q$ there is a $Y\in\Delta\cap L$ such that

Since $\phi$ is monotone and homogeneous of degree $N$ (see Section 6.2) , we have

(7.3) Proof of Theorem 1.1

The upper bound follows immediately from the standard generating function expression:

and the some is taken over all pairs of positive integer $m$-vectors $R=\left(r_{1},\ldots,r_{m}\right)$ and $n$-vectors $C=\left(c_{1},\ldots,c_{n}\right)$ such that $r_{1}+\ldots+r_{m}=c_{1}+\ldots+c_{n}$.

Let us prove the lower bound. By Lemma 1.4 the minimum of

on the open cube $0<x_{i},y_{j}<1$ for all $i,j$ is attained at a certain point

Equations (7.3.1) can also be obtained by setting the gradient of $\ln F$ to 0.

Hence $\dim L=(m-1)(n-1)$ and $A\in L$ by (7.3.1).

By (6.4.2), the density $\phi=\phi_{R,C}$ is constant on $L$ and equal to

By Part (1) of Theorem 3.1, the volume of the section $\Delta\cap L$ within a factor of $(N+mn)^{O(m+n)}$ is at least

More precisely, for $k=d-1-\dim(\Delta\cap L)$ we have $k=m+n-1$ or $k=m+n-2$ and

Choosing $\epsilon=1/(N+mn)$ in Lemma 7.2, we estimate the integral

within a factor of $N^{O(m+n)}$ from below by

provided $m+n\geq 10$. Hence by (6.3.2) the number $\#(R,C)$ is estimated from below within a factor of $(N+mn)^{O(m+n)}$ by

where “$\approx$” stands for an approximation within a $N^{O(m+n)}$ factor.

The proof of Theorem 1.3 is a straightforward modification of the proof of Theorem 1.1.

(7.4) Proof of Theorem 1.3

The upper bound follows from the generating function expression

Let us prove the lower bound. Since $T(R,C;W)$ is a polynomial in $W$, without loss of generality we assume that $W$ is a strictly positive matrix. Let

In the space of matrices, let us consider the standard simplex $\Delta$ and the matrix $A=\left(\alpha_{ij}\right)$

As in the proof of Theorem 1.1, we check from (7.4.1) that indeed $A\in\Delta$. Let

Then $A\in L$, the value of $\phi_{R,C;W}$ on $\Delta\cap L$ is constant and equal to

see (6.5.2)-(6.5.3). Next, we use the lower bound in (6.5.1) and the proof proceeds as for Theorem 1.1. ∎

Acknowledgments

This work grew out of a joint project with Alex Samorodnitsky, and at an earlier stage also with Alexander Yong, on constructing computationally efficient algorithms for enumeration of contingency tables, see [BSY07]. I am grateful to Keith Ball and Matthieu Fradelizi for teaching me methods to estimate volumes of sections of convex bodies. I benefitted from conversations with Alex Samorodnitsky, Imre Bárány, and Roy Meshulam.