Doubling constant (dimension) of $R^3$ under $L_1$ metric What is the doubling constant of $\mathbb{R}^3$ under $L_1$ metric?
i.e. how many $L_1$ balls of radius $1/2$ are needed to cover an $L_1$ ball of radius $1$?
Note that an $L_1$ ball in $\mathbb{R}^3$ is in the shape of a regular octahedron, but we are not allowed to rotate it in the space.
 A: Throughout this answer when I use the term ball, I mean a closed ball in the $L^1$ norm.
Below I show that it takes at least $8$ and no more than $18$ $\tfrac{1}{2}$-balls to cover the unit ball in $\mathbb{R}^3$. I conjecture that the latter is optimal.
Lower bound
The volume of an $r$-ball is $\propto r^3$. So, we will need at least $8$ of the smaller balls to cover the unit ball.
Upper bound
I have noticed a configuration which covers the unit ball centred at the origin with $18$ $\tfrac{1}{2}$-balls. The $\tfrac{1}{2}$-balls are centred at the points
$$A=\{(\pm\tfrac{1}{2},0,0),(\pm\tfrac{1}{4},\pm\tfrac{1}{4},0)+\textrm{permutations}\}$$
To see that these cover the unit ball, we will show that for $P=(x,y,z)\in \mathbb{R}^3$ with $\|P\|_1\le 1$ one of these vectors is at most $\tfrac{1}{2}$ distance away. WLOG we can assume that $0\le x\le y\le z$ as the points of $A$ are closed under the isometries $x\mapsto -x$ and permutation of coordinates. $P$ is in one of the $\tfrac{1}{2}$ balls centred at $(0,\tfrac{1}{4},\tfrac{1}{4})$ and $(0,0,\tfrac{1}{2})$. Indeed if $z\ge \tfrac{1}{2}$, then
$$|x|+|y|+|z-\tfrac{1}{2}|=|x|+|y|+|z|-\tfrac{1}{2}\le \tfrac{1}{2}$$
as $|x|+|y|+|z|\le 1$.
Otherwise $0\le z\le \tfrac{1}{2}$ implies $|z-\tfrac{1}{4}|\le \tfrac{1}{4}$. If also $y\le \tfrac{1}{4}$, then
$$|x|+|y-\tfrac{1}{4}|+|z-\tfrac{1}{4}|=x-y+\tfrac{1}{4}+|z-\tfrac{1}{4}|\le \tfrac{1}{2}$$
because $y\ge x\ge 0$.
Finally we are left with the case that $y\ge \tfrac{1}{4}$ and $y\le z\le \tfrac{1}{2}$ so
$$|x|+|y-\tfrac{1}{4}|+|z-\tfrac{1}{4}|=|x|+|y|-\tfrac{1}{4}+|z|-\tfrac{1}{4}\le \tfrac{1}{2}$$
as $|x|+|y|+|z|\le 1$.
Other dimensions
In two dimensions, it requires exactly $4$ balls to cover. The lower bound in any dimension $d$ is $2^d$ (as measure scales like $r^d$), of course. We can derive a very crude upper bound of $(2d)^d$ in any dimension via the relation
$$\|P\|_\infty\le \|P\|_1\le d\|P\|_\infty$$
holding in $\mathbb{R}^d$. It follows that the $L^1$ ball of radius $r$ is between the $L^\infty$ balls (hypercubes) of radii $r/d$ and $r$. Since the unit $L^\infty$ ball, is covered by $n^d$ $L^\infty$ balls of radius $r=1/n$, we can put the unit $L^1$ ball inside the unit $L^\infty$ ball, cover this with $n^d$ $L^\infty$ balls of radius $r=1/n$ and put each of these inside an $L^1$ ball of radius $r=d/n$. So, to get $r=\tfrac{1}{2}$ we need $n=2d$ and the number of balls is $(2d)^d$.
Original weaker upper bound
My original answer contained an upper bound of $27$ balls, using the tesselation of $\mathbb{R}^3$ by the truncated octahedron here https://en.wikipedia.org/wiki/Bitruncated_cubic_honeycomb
This gives a covering of the $\mathbb{R}^3$ by octahedra, and I used this to get an upper bound of $27$ balls. I have deleted this, as the bound has been considerably improved.
