Number of Distinct Words of arbitrary length $k$ in Euclidean N-Space (i.e; $\mathbb{Z}^N$)

Question

Consider the $N$ dimensional Euclidean Space ($\mathbb{Z}^N$) with it's generating set $G=\{g_1,\cdots,g_N\}$ (and their inverses obviously!), how many distinct words of arbitrary length $k$ are there?
Note: $g_i$ is the basis in the $i^{th}$ direction (i.e; a vector of length $N$ with zeros and $1$ as the $i^{th}$ element).

• I understand that $Z^N$ is a free abelian group. As an easy example consider a simple case of $Z^2$ with $G = \{g_1,g_2\}$,I know that $g_1 g_2 = g_2 g_1$ and should NOT be counted twice.
• Words are reduced before measuring their length

So with these in mind I thought it is a good practice to start with $N=2$ and arbitrary length $k$ and actually count the number of the words of length $k$ in $\mathbb{Z}^2$: the words of length $k$ in $\mathbb{Z}^2$ all lies on a diamond with vertices at $\{(0,k),(0,-k),(k,0),(-k,0)\}$. So we have $4(k-1)+4 = 4k$ distinct words of arbitrary length $k$ in $\mathbb{Z}^2$.

Next I did the same for arbitrary length $k$ in $\mathbb{Z}^3$. Now the shape would be an octahedron with vertices at $\{(0,0,k),(0,0,-k),(0,k,0),(0,-k,0),(k,0,0),(-k,0,0)\}$ and all the distinct words of length $k$ would be on the surface of this octahedron. For this I basically counted using slicing perpendicular to $z$ axis. For example count all the words of length $k$ in $\mathbb{Z}^3$ where $g_3$ or it's inverse are never used. This approach would turn the problem into a counting problem in $\mathbb{Z}^2$ which we already know the answer to: so the total number of distinct(unique) words of arbitrary length $k$ in $\mathbb{Z}^3$ would be $\sum_\limits{m = -(k-1)}^{m=(k-1)}4(k-|m|)+2 = \sum_\limits{i=1}^{k}(4i^2+2)$.
After this is where I am getting stuck as I know continuing this approach would yield formulas that grow in complexity with every additional dimension. (I actually went through $N=3,4$ and kind of feel like that the general formula should be of the form $2^N k^{N-1} + \text{some lower order terms}$,but this is just a guess.

I am looking for ideas on how to better approach this or reference to any paper investigating the same problems.

Answer 1

I would like to show you how to solve your question and similar ones using the DSV method (due to Delest, Schützenberger and Viennot). My introduction to this method was [1], the standard reference is [2].

So given some $k\in\mathbb{N}$ and the generating set $\mathcal{G}=\{g_1, \ldots, g_n\}$, how many unique group elements in $\mathbb{Z}^n$ are there whose shortest representation has word length $k$?

The following four steps lead us towords an answer (= a generating function).

1. Construct a normal form for elements of $\mathbb{Z}^n$.
2. Construct a context free grammar.
3. Convert the grammar into a system of equations.
4. Solve the system of equation.

Step 1. When we say that we want to construct a normal form for the elements of a group, what we are looking for is a sort of canonical unique representation of the group elements as words over the groups generating set. These can also be thought of as "canonical paths" in the Cayley graph.

In our case of $\mathbb{Z}^n$, one relatively obvious strategy is to start at the origin and first walk in direction $g_1$ as far as necessary, then in direction $g_2$ and so on. This gives us the map

$$(z_1, z_2, \ldots, z_n) \mapsto g_1^{z_1}g_2^{z_2}\cdots g_n^{z_n}.$$

Step 2. Now we construct a context free grammar (= a set of production rules for words). There are two necessary properties our grammar ought to have: 1. It should of course produce a representation of every element in the group and 2. the way a word is produced should be unique.

In our case the grammar

$$\begin{aligned}\boldsymbol{S} &\longrightarrow \boldsymbol{E}_1\boldsymbol{E}_2\cdots \boldsymbol{E}_n \\ \boldsymbol{E}_1 &\longrightarrow g_1\boldsymbol{E}_1^+ \mid g_1^{-1}\boldsymbol{E}_1^- \mid \varepsilon \\ \boldsymbol{E}_1^+ &\longrightarrow g_1\boldsymbol{E}_1^+ \mid \varepsilon \\ \boldsymbol{E}_1^- &\longrightarrow g_1^{-1}\boldsymbol{E}_1^- \mid \varepsilon \\ &\quad\vdots \\ \boldsymbol{E}_n &\longrightarrow g_n\boldsymbol{E}_n^+ \mid g_n^{-1}\boldsymbol{E}_n^- \mid \varepsilon \\ \boldsymbol{E}_n^+ &\longrightarrow g_n\boldsymbol{E}_n^+ \mid \varepsilon \\ \boldsymbol{E}_n^- &\longrightarrow g_n^{-1}\boldsymbol{E}_n^- \mid \varepsilon\end{aligned}$$

works as desired.

Step 3. To transform a grammar into a system of equations, substitute all grammar symbols as per the following table.

Replace...	with...
the empty word $\varepsilon$	the integer 1
each terminal letter $g$	the formal variable $x$
the production arrow $\longrightarrow$	an equal sign =
each grammar variable $\boldsymbol{V}$	a function $V(x)$
the exclusive or |	the addition symbol +
concatenation	commutative multiplication

Applying this to our grammar we get

$$\begin{aligned} S(x) &= E_1(x)E_2(x)\cdots E_n(x) \\ E_1(x) &= xE_1^+(x) + xE_1^-(x) + 1 \\ E_1^+(x) &= xE_1^+(x) + 1 \\ E_1^-(x) &= xE_1^-(x) + 1 \\ &\:\:\vdots \end{aligned}$$

Step 4.

Theorem. Solving the resulting system for $S(x)$ gives the growth series for the grammar productions.

So to solve for $S(x)$ is what we do. First we get

$$E_i^\pm(x)= \frac{1}{1-x},$$

for all $i=1, \ldots, n$. Substituting this into $E_i(x)$ we get

$$E_i(x) = \frac{1+x}{1-x}$$

and so, finally,

$$S(x)=\left( \frac{1+x}{1-x} \right)^n.$$

---

At the end, let's make a quick sanity check. For $n=2$ we get the sequence

$$1, 4, 8, 12, 16, 20, \ldots.$$

This agrees with the sequence you came up with, except it also counts the one word of length 0. For $n=3$ we get

$$ 1, 6, 18, 38, 66, 102, \ldots.$$

According to the OEIS this is the sequence $a(n)=4n^2+2$, so your formula would actually be the cumulative growth series, which makes sense if you think about your approach. You can try different values for $n$ for yourself on WolframAlpha.

The next step would be to find a closed form expressions for these sequences. Unfortunately, I myself do not know enough about this business (yet), so others have to be your teacher. I suspect though that browsing the OEIS should give you plenty of hints.

---

[1] E. Freden. Growth of Groups. In Office Hours with a Geometric Group Theorist, pages 237-266. Princeton University Press, 2017.

[2] N. Chomsky and M. P. Schützenberger. The algebraic theory of context-free languages. In Computer programming and formal systems, pages 118–161. North-Holland, Amsterdam, 1963.

Answer 2

Your function, which I shall denote $\phi(k)$, is closely related to the ordinary growth function of $G$ with respect to the generating set $\{g_1,...,g_N\}$, which I shall denote $\gamma(k)$. This function $\gamma(k)$ is defined to be the number of group elements $g \in G$ such that the least length of a reduced word representing $g$ is $\le k$; also, $\gamma(k)$ is easily seen to be equal to the number of group elements which are represented by reduced works of length $\le k$.

One relation between your function $\phi(k)$ and the growth funcion $\gamma(k)$ is given by the inequalities $$\gamma(k) - \gamma(k-1) \le \phi(k) \le \gamma(k) $$ One can use this, combined with facts drawn from the deep literature on $\gamma(k)$, to make deductions about $\phi(k)$.

Here's just one very simple such deduction, following up on your idea to investigate $\mathbb Z^2$ and $\mathbb Z^3$. If $G = \mathbb Z^N$ and $\{g_1,\ldots,g_N\}$ is the standard basis for $\mathbb Z^N$ then it is known that $\gamma(k)$ is exactly equal to a certain polynomial of degree $N$. It follows that $\gamma(k)-\gamma(k-1)$ is exactly equal to a certain polynomial of degree $N-1$. Therefore, $\phi(k)$ has a polynomial lower bound of degree $N-1$ and a polynomial upper bound of degree $N$.

Clearly there's more to be investigated: even in this very simple example, the exact relation between $\phi(k)$ and $\gamma(k)$ is not entirely clear yet. I would guess that for this example $\phi(k)$ has a stronger lower bound, namely one which is polynomial of degree $N$. And, of course, as you have already started for the cases $N=2$ and $N=3$, one might wish to get an exact expression for $\phi(k)$; for instance, is it equal to a polynomial of degree $N$?