The intersection of two $l_1$ balls

Question

Let $B_1$ and $B_2$ be two balls in $\mathbb{R}^n$ with respect to the $l_1$ norm that have different radii and different centers. Is there an upper bound for the number of vertices that $B_1\cap B_2$ has?

Answer 1

There is an exponential upper bound of $9^n$, since every vertex of $B_1 \cap B_2$ is the intersection of a $k$-face of $B_1$ and a $(n-k)$-face of $B_2$ for some $k$, and the $\ell_1$-ball has $3^n$ faces (all dimensions counted together).

You cannot do better for large $n$ except for the value of the constant $9$. Indeed, let $B_1$ be $\ell_1$ ball of center $(\frac 1n,\cdots,\frac 1n)$ and radius $1$, and $B_2=-B_1$. Then $B_1 \cap B_2$ is the $(n-1)$-dimensional polytope defined as $$ \{ (x_1,\dots,x_n) \, : \, \sum x_i=0, \ |x_i| \leq 1/n \} .$$ If (for simplicity) $n$ is even, it has $\binom{n}{n/2} \geq (2-o(1))^n$ extreme points, namely those vectors with $|x_i|=1/n$ and evenly distributed signs.

Remarkably, with rotated balls centered at the origin, you get the same phenomenon. Indeed the intersection $K$ of the standard $\ell_1$ ball with a randomly rotated copy of itself has (with high probability) the property that $\frac{1}{\sqrt{n}} B \subset K \subset \frac{C}{\sqrt{n}} B$ for some constant $C$ (here $B$ is the Euclidean unit ball). This is known as the "global form of Kashin's theorem", see Theorem 5.5.4. in [1]. That sandwiching forces $K$ to have at least $\exp(cn)$ vertices for some other constant $c$ (essentially because a spherical cap of fixed angle less than $\pi/2$ covers an exponentially small proportion of the sphere as $n \to \infty$).

[1] S. Artstein-Avidan, A. Giannopoulos, V. Milman, Asymptotic Geometric Analysis, Part I