= Word metric balls in the integer lattice
{title2=$B_S(0,r)$}
= Lattice word metric ball
{synonym}
The additive <group> $\mathbb Z^2$ gives a useful way to see what a <word metric> measures. Let $e_1=(1,0)$ and $e_2=(0,1)$, and choose the four-move <generating set of a group> $S=\{\pm e_1,\pm e_2\}$. Its <Cayley graph> is the <square lattice>. Each move changes exactly one <coordinate> by one, so the <word length> is the <L1 norm>, and the <word metric> is <Manhattan distance>:
$$
|(m,n)|_S=|m|+|n|.
$$
At least this many moves are necessary, and moving horizontally then vertically attains the bound. Bridson gives this <square lattice> as a basic <Cayley graph> example.https://people.maths.ox.ac.uk/bridson/papers/BATH97.pdf[Bridson, Example 1.8]{ref}
Now allow all eight neighbouring lattice points as moves:
$$
T=\{\pm e_1,\pm e_2,\pm(1,1),\pm(1,-1)\},\qquad |(m,n)|_T=\max\{|m|,|n|\}.
$$
Each <coordinate> changes by at most one per move. Use diagonal moves until the smaller displacement is exhausted, then use axis moves: the resulting <word length> is the <maximum norm>, and the <word metric> is <Chebyshev distance>. From $(0,0)$ to $(2,3)$, an $S$-route has five steps, while the $T$-route $(0,0),(1,1),(2,2),(2,3)$ has three.
The closed <word metric balls> $B_S(0,r)=\{v\in\mathbb Z^2:d_S(0,v)\leq r\}$ consist of lattice points inside a diamond for $S$, and inside an axis-aligned square for $T$. For every nonnegative <integer> radius $r$,
$$
\#B_S(0,r)=1+\sum_{k=1}^{r}4k=1+2r(r+1),\qquad \#B_T(0,r)=(2r+1)^2.
$$
The diamond has $4k$ lattice points at <word length> $k>0$; the square has $2r+1$ choices for each <coordinate>. At radius three the counts are $25$ and $49$. These are discrete <closed balls> for <Manhattan distance> and <Chebyshev distance>; an <Euclidean distance> bound would instead select lattice points inside a <Euclidean disk>.
\Image[/word-metric-lattice-balls.png]
{title=Radius-three <word metric balls> in the <integer lattice>: a diamond with 25 points and a square with 49 points, with routes to $(2,3)$}
Back to article page
