Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)$.

share|improve this question

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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