Progressive dilations of \( P_n(S) \) in \( (\mathbb{Z}^3,+) \)

In the commutative setting, vector addition over \( \mathbb{Z} \) is straightforward.
Given two vectors \( v,w \in \mathbb{Z}^3 \), vector addition is simply defined as
addition component-wise. In fact, \( (\mathbb{Z}^3, +) \) actually forms an abelian group,
i.e. \( v + w = w + v \). So now consider some basis set of vectors, say \[ S = \{ (0,0,0),
(1,0,0), (0,1,0), (0,0,1) \}. \]
As an example, we will generate all *words* of length \( k \). To find these, first
take the \( k \)-fold product \( \underbrace{S \times S \times \ldots \times S}_{k \text{ times}} \).
Then for each element in \( S \times S \times \ldots \times S \), compute
\( s_1 \star s_2 \star \ldots \star s_k \). This will give an element in \( (\mathbb{Z}^3, \star) \).
For \( k = 2 \), this yields
\[ \begin{align}
(0,0,0) + (0,0,0) & = (0,0,0), \\
(0,0,0) + (1,0,0) & = (1,0,0), \\
(0,0,0) + (0,1,0) & = (0,1,0), \\
(0,0,0) + (0,0,1) & = (0,0,1), \\
(1,0,0) + (0,0,0) & = (1,0,0), \\
(1,0,0) + (1,0,0) & = (2,0,0), \\
(1,0,0) + (0,1,0) & = (1,1,0), \\
(1,0,0) + (0,0,1) & = (1,0,1), \\
(0,1,0) + (0,0,0) & = (0,1,0), \\
(0,1,0) + (1,0,0) & = (1,1,0), \\
(0,1,0) + (0,1,0) & = (0,2,0), \\
(0,1,0) + (0,0,1) & = (0,1,1), \\
(0,0,1) + (0,0,0) & = (0,0,1), \\
(0,0,1) + (1,0,0) & = (1,0,1), \\
(0,0,1) + (0,1,0) & = (0,1,1), \\
(0,0,1) + (0,0,1) & = (0,0,2).
\end{align} \]
Getting rid of duplicates, this yields
\[ \begin{align}
P_2(S) = \{ & (0,0,0) \\
& (0,0,1) \\
& (0,0,2) \\
& (0,1,0) \\
& (0,1,1) \\
& (0,2,0) \\
& (1,0,0) \\
& (1,0,1) \\
& (1,1,0) \\
& (2,0,0) \},
\end{align} \]
where \( P_k(S) \) denotes the polytope generated as the \( k \)th dilate of
the basis set \( S \). In other words, \( P_k(S) \) is the set of points realized as words of
length \( k \) generated by elements of the basis set \( S \). If we let \( \mathcal{B} \) be an aribitrary
(finite) basis set with \( \lvert \mathcal{B} \rvert = n \) and compute the words of length \( k \), then
there are \( n(n-1)\ldots(n-k+1) \) evaluations to compute. In this example, the number of points contained
in \( P_k(S) \), which we will call the *volume*, is given by \( V = \binom{k+2}{3} \). Furthermore,
it can be seen that there are no "missing spots" in the \( P_k(S) \), so we will say \( P_k(S) \) is
*saturated* if this is the case. Additionally, the outer face of \( P_k(S) \) can be desribed by the
function \( z = f(x,y) = k-x-y \). These properties of \( P_k(S) \) motivate the study of polytopes
generated in the setting of the Heisenberg group.

To get to the Heisenberg group, we basically do normal vector addition, but now with a
twist:
\[ \star \colon \mathbb{Z} \times \mathbb{Z} \longrightarrow \mathbb{Z}, \quad (x, y, z) \star (x', y', z') = (x+x', y+y', z+z'+xy'). \]
This new operation is *almost* normal vector addition, except now there is an extra
\( xy' \) tacked onto the \( z \)-component. Because of this new twist, \( (\mathbb{Z}^3, \star) \)
forms a noncommutative group. We want to explore this group some more, so now we will consider the
we will choose a basis set of vectors, say \( S \) (as we did before). As an example, consider again \( k=2 \):
\[ \begin{align}
(0,0,0) \star (0,0,0) & = (0,0,0), \\
(0,0,0) \star (1,0,0) & = (1,0,0), \\
(0,0,0) \star (0,1,0) & = (0,1,0), \\
(0,0,0) \star (0,0,1) & = (0,0,1), \\
(1,0,0) \star (0,0,0) & = (1,0,0), \\
(1,0,0) \star (1,0,0) & = (2,0,0), \\
(1,0,0) \star (0,1,0) & = (1,1,1), \\
(1,0,0) \star (0,0,1) & = (1,0,1), \\
(0,1,0) \star (0,0,0) & = (0,1,0), \\
(0,1,0) \star (1,0,0) & = (1,1,0), \\
(0,1,0) \star (0,1,0) & = (0,2,0), \\
(0,1,0) \star (0,0,1) & = (0,1,1), \\
(0,0,1) \star (0,0,0) & = (0,0,1), \\
(0,0,1) \star (1,0,0) & = (1,0,1), \\
(0,0,1) \star (0,1,0) & = (0,1,1), \\
(0,0,1) \star (0,0,1) & = (0,0,2).
\end{align} \]
Getting rid of duplicates, this yields
\[ \begin{align}
P_2(S) = \{ & (0,0,0) \\
& (0,0,1) \\
& (0,0,2) \\
& (0,1,0) \\
& (0,1,1) \\
& (0,2,0) \\
& (1,0,0) \\
& (1,0,1) \\
& (1,1,0) \\
& (1,1,1) \\
& (2,0,0) \},
\end{align} \]
Since \( (\mathbb{Z}^3, \star) \) is noncommutative, it is important that each word is evaluated according
to the order of the elements. We can also visualize these results as points in \( \mathbb{Z}^3 \), as shown
in the slideshow below. If we let \( \mathcal{B} \) be an aribitrary
(finite) basis set with \( \lvert \mathcal{B} \rvert = n \) and compute the words of length \( k \), then
there are \( n^k \) evaluations to compute. For large \( k \), this task becomes intractable.

We can ask the same questions about \( P_k(S) \) as we did in the commutative setting:

- What is the volume of \( P_k(S) \)?
- Is \( P_k(S) \) saturated?
- Can we describe the
*ceiling function*of \( P_k(S) \)?