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

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=(aij)∈ℝm×n is defined as the maximum of |∑iI,jJaij| 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/mnc/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!)3. 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/mnd 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.

-

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.