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∈J}*a*_{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*) = (2*n*)!/(*n*!)^{3}. Using this, we have that *V*(*m*, *n*) ≤ (*V*(1, *n*))^{m} = ((2*n*)!)^{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.