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.
Best Answer
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).
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.
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.
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.