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.

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

| cite | improve this answer | |
  • $\begingroup$ Thank you for the answer! Although I have to admit that most results referred to in your other answer are over my head, I will try (hopefully in a few weeks) to understand at least part of it. $\endgroup$ – Tsuyoshi Ito Oct 11 '11 at 17:51
  • $\begingroup$ I see you are interested in quantum complexity, so maybe a source is arxiv.org/pdf/1106.2264. We apply a more sophisticated version of the argument to a problem in quantum information, and we introduce all the material we need in Appendices. $\endgroup$ – Guillaume Aubrun Oct 12 '11 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.