3
$\begingroup$

The following question arises, for me, from mathematical music theory:

Write $({\Bbb Z}^n,E_n)$ for the Cayley graph of ${\Bbb Z}^n$ relative to standard free generators.

Given a subgroup $L$ of ${\Bbb Z}^n$ of finite index, how ought one efficiently count and/or enumerate, up to translation, the connected (as vertex-induced subgraphs) fundamental domains for the action of $L$ on $({\Bbb Z}^n,E_n)$.

$\endgroup$

1 Answer 1

1
$\begingroup$

An inefficient way for enumerating all connected fundamental domains is by remarking that they are all contained (up to translation) in the ball of radius at most $(l+1)/2$ (with respect to word length in generators) at the origin where $l$ is the index of the subgroup $L$. It is thus enough to consider all connected subgraphs having $l$ vertices contained in this ball and to check that vertices of such a subgraph represent distinct classes modulo $L$.

A perhaps more effective idea is as follows: Call two connected fundamental domains $D_1$ and $D_2$ adjacent if $D_1\cap(D_2+A)$ contains $l-1$ elements for a suitable vector $A$ (where $l$ is the index of the subgroup). This turns the set of all connected fundamental domains (considered up to translation) into a finite graph.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.