Sizes of Hamming balls on the discrete torus

Question

Consider the discrete torus $\mathbb Z^2_k $, with $k$ even, i.e. the graph with vertex set $\{0,1,\dots, k-1\} \times \{0,1,\dots, k-1\}$ and edges between any pair of vertices which differ in exactly one coordinate by $1$ (modulo $k$).

Denote by $d(0,v)$ the graph distance on $\mathbb Z^2_k $ between the origin, that is the vertex of coordinate $(0,0)$ and the vertex $v$. Let $B_r$ be the Hamming ball of radius $r$ centered at the orgin, defined as $$ B_r:=\{ v \in \mathbb Z^2_k ~:~d(0,v) \leq r\}, $$ and denote by $b(r):=|B_r|$ its cardinality.

Is there a way to characterize/describe/compute the sequence $b(1),\dots,b(k)$? If $r<k/2$, then the toroidal boundary has no effect on the Hamming balls and thus $b(r)=1+4 \cdot \sum_{i=1}^r i$. But what can be said in the case $r \geq k/2$?

Answer 1

Hints: Let $m$ be the special element $m=(k/2,k/2)$. I denote by $B(0;r)$ (resp. $B(m,r)$) the ball with radius $r$ centered at $0$ (resp. $m$), so your $B(r)$ is my $B(0;r)$.

• Show that for all the vectors $v$ you have $$d(0,v)+d(m,v)=k.$$
• Show that for all $r, 0\le r\le k$, $v\in B(0;r)$ if and only if $v\notin B(m;k-1-r).$
• Show that for all $r, 0\le r\le k$, $v\in B(0,r)$ if and only if $v+m\in B(m,r)$.
• Show that for all $r, 0\le r\le k$, $b(r)+b(k-1-r)=k^2$.