Consider a finite subset $S$ of $\mathbb Z^n$ such that $-s\in S$ whenever $s\in S$ and $S$ generates $\mathbb Z^n$. What is a norm on $\mathbb R^n$ whose unit ball is precisely the convex hull of $S$?
In $\mathbb R^2$ we can see:
- $S=\{ \pm(1,0),\pm(0,1)\}$ corresponds to the metric $\|(x,y)\|=|x|+|y|$
- $S=\{ \pm(1,1),\pm (1,0), \pm(0,1) \}$ corresponds to $\|(x,y)\|=\frac{1}{2}( |x-y|+|x|+|y|)$
It looks like if $S=\{ \pm(n_i,m_i):i=1,\dots,k\}$ in $\mathbb R^2$ then the norm is $$ \|(x,y)\|= \sum_i c_i |m_ix-n_iy|$$ where the constants $c_i$ are such that $\|(n_i,m_i)\|=1$ for all $i$. Is there an easy way to see this and generalise to $n$ dimensions?
Note: This norm will give us lower and upper bounds for the word metric in the Cayley Graph obtained by $S$. Also, the distance of two nodes of the graph is the same in both metrics.
As StevenTaschuk proposed, we can take $$\|x\| = \inf \{ \sum_i \lambda_i :x=\sum_i \lambda_is_i, s_i\in S, \textrm{ and }\lambda_i\geq 0\}$$ for $x\in \mathbb R^n$. Each $x=(x_1,\dots,x_n)\in \mathbb R^n$ can be obtained as $\sum_{i=1}^n \tilde \lambda_iz_i$ for $\tilde \lambda_i\geq 0$ and $z_i\in \mathbb Z^n$. Since $S$ generates $\mathbb Z^n$, we can write each $x\in \mathbb R^n$ as $x=\sum_i \lambda_is_i, s_i\in S, \textrm{ with }\lambda_i\geq 0$. Therefore, $\|\cdot \|$ is well-defined and is always finite. Now it is easy to check that it is a norm. Also, one can see that the infimum is attained.
Regarding the unit ball, let $\|x\|\leq 1$, so there exist $\lambda_i\geq 0$ such that $x=\sum_i \lambda_i s_i$ and $\sum_i \lambda_i\leq 1$. Note that $0$ is in the convex hull of $S$, since it is the midpoint of some $s\in S$ and $-s\in S$. Thus we can write $$x=\sum_i \lambda_is_i+ (1-\sum_i \lambda_i) \cdot 0$$ and this shows that $x$ is a convex combination of $s_i$ and $0$.
Conversely, if $x=\sum_i \lambda_is_i$ with $\sum_i \lambda_i=1$ then trivially $\|x\|\leq 1$. This completes the proof.
Furthermore, it is clear from the way we defined this norm that the induced metric agrees (on $\mathbb Z^n$) with the word metric of the Cayley graph of $S$.