The volume of the “unit ball” in $\mathbb{R}^{m\times n}$ with respect to the cut norm

Question

This question is inspired by the question “ε-nets with respect to the cut norm” by the user Aaron, which had been reposted to cstheory.stackexchange.com.

The cut norm ||A||_C of a matrix A=(a_ij)∈ℝ^m×n is defined as the maximum of |∑_i∈I,j∈Ja_ij| over the subsets I⊆{1,…,m} and J⊆{1,…,n}. The “unit ball” in ℝ^m×n with respect to the cut norm is the convex polytope P(m, n) = {A∈ℝ^m×n: ||A||_C≤1}. Let V(m, n) be the volume of this polytope P(m, n).

Since P(m, n) contains [0, 1/mn]^m×n, we have that V(m, n) ≥ 1/(mn)^mn. In other words, (V(m, n))^1/mn ≥ 1/mn.

Question. Is this lower bound on (V(m, n))^1/mn tight up to a constant factor? In other words, does there exist a constant c>0 such that for every m,n≥1, it holds that (V(m, n))^1/mn ≤ c/mn?

This lower bound is indeed tight up to a constant factor if one of m and n is bounded by a constant. This can be shown as follows. In an answer on cstheory.stackexchange.com, I gave a sketch of a proof that V(1, n) = (2n)!/(n!)³. Using this, we have that V(m, n) ≤ (V(1, n))^m = ((2n)!)^m/(n!)^3m. By using Stirling’s formula, we obtain that there exists an absolute constant d>0 such that for every m and n, it holds that (V(m, n))^1/mn ≤ d min{1/m, 1/n}.

A positive answer to this question improves the lower bound on Aaron’s question to match the upper bound up to a constant factor.

Answer 1

A standard argument (Lemma 3.1 here) shows that the cut-norm is 4-equivalent to the operator norm from $\ell_{\infty}^m$ to $\ell_1^n=(\ell_\infty^n)^*$. Therefore the volume you ask is almost the same (up to a factor $4^{mn}$) as the volume of the unit ball in the projective tensor product $\ell_{\infty}^m \otimes_\pi \ell_\infty^n$. This is exactly this question (at least for $m=n$), and I gave an answer saying basically that (from general theorems) your lower bound on $V(m,n)^{1/mn}$ is sharp up to a logarimthic factor.

I guess this logarithm is not necessary, but I don't know how to remove it.