tesselations in $1$ dimension (i.e., tiling a quotient group of integers with same-shaped subsets)

104 Views Asked by At

I am interested in the following problem which relates to music and serialism. It is akin to tesselating the plane with congruent, non-overlapping shapes, but I want to apply "same-shaped" subsets of the integers to disjointly tesselate or "tile" the $1$-dimensional lattice of integers.

I'll start with an example. Suppose we are working in a quotient group $Z6$, that is, all integers are mapped to the numbers $[0, 1, 2, 3, 4, 5]$, depending on congruence modulo $6$. Now, $Z6$ can be "tiled" with [$0, 1]$ as follows: $[0, 1], [2, 3]$, and $[4, 5]$. It can be "tiled" with $[0, 3]$ as follows: $[0, 3], [1, 4]$, and $[2, 5]$. It can be "tiled" with $[0, 1, 2]$ and [$3, 4, 5]$; it can also be "tiled" with $[0, 1, 3]$ and $[5, 4, 2]$, considering the second collection as an "upside-down" (i.e,. inverted) form of the first. It cannot be tiled by $[0, 2]$, since $[4]$ has no partner that isn't already taken (i.e., neither $[2, 4]$ nor [$4, 0]$ would be disjoint with $[0, 2]$).

In $12$-tone serialism, we talk about self-combinatorial hexachords; for example, $[0, 2, 4, 7, 9, 11]$ is self-combinatorial with $[6, 8, 10, 1, 3, 5]$, modulo $12$. Moreover, several smaller set-classes can be combined with musical transpositions of themselves (read as "add the same number to each element in the array, modulo $12$) or inversions of themselves (read as, multiply every element in the array by -1) to form the "aggregate" (that is, all 12 pitch classes are covered once). An example would be $[0, 1, 5]$, $[3, 4, 8], [6, 7, 11], [9, 10, 2]$. These sort of things have been studied in great detail over the past $80$ years or so.

I feel certain that mathematicians must have studied collections like this in general, but for the life of me, I can't figure out what they call these things! Obviously, brute force is okay for low values ($Z6, Z8$, etc.) but as the number of elements gets higher, it is difficult to be certain I am being thorough. The terms "tesselation" and "tiling" seem to only apply to $2$-dimensions and up! Also, I'm not sure what to call a $1$-dimensional lattice of integers other than a quotient group. And though this must be related to partition theory, I'm still at a loss to find any information. Does anybody have any tips?

Much appreciated!

Jason

1

There are 1 best solutions below

5
On

You seem to have a block system for cyclic subgroups. Let's go over terms.

A group action of $G$ on a set $X$ is a way of interpreting $G$'s elements as permutations of $X$, and interpreting $G$'s binary operation as composition of functions. In other words, it is a group homomorphism $G\to\mathrm{Perm}(X)$. It needn't be "faithful" - it could have a kernel, in which case different elements of $G$ can act as the same permutation of $X$. An action can equivalently be defined as a map $G\times X\to X$, written $(g,x)\mapsto gx$ for simplicity usually.

As an example, consider the rotational symmetry group $G$ of the 3-dimensional cube. Let $V$ be the set of vertices, $E$ the set of edges, $F$ the set of faces, $A$ the set of axes, $D$ the set of diagonals through the cube, and $T$ the pair of inscribed tetrahedra. We have group actions of $G$ on each of these sets. In fact, the action of $G$ on $D$, that is the map $G\to\mathrm{Perm}(D)$, is an isomorphism, so $G\cong S_4$. The homomorphism from $G$ to $\mathrm{Perm}(A)$ is onto, and $|A|=3$, so we get a map $S_4\to S_3$; its kernel is the Klein four group $V_4$, and this is the only time a symmetric group $S_n$ has a (proper, nontrivial) normal subgroup other than the alternating group $A_n$. The map $G\to\mathrm{Perm}(T)$ is really just the sign map $\mathrm{sgn}:S_4\to\{\pm1\}$ since $|T|=2$ and the kernel is $A_4$ (the rotational symmetry group of a tetrahedron).

The orbit of $x\in X$ with respect to a group action $G\curvearrowright X$ is the subset $\mathrm{Orb}(x)=\{gx:g\in G\}$. The whole set $X$ is the disjoint union of all the orbits it contains. (No two distinct orbits share any elements in common, and every element $x$ is in its own orbit $\mathrm{Orb}(x)$.) As a fun geometry exercise, one may take individual elements $g$ from the rotational symmetry group $G$ of the cube (as above), and look at the orbits of the cyclic group $\langle g\rangle$ acting on those sets $V,E,F,A,D,T$. (The orbits of the cyclic subgroup generated by an element $g$ are called $g$'s cycles and are present in the cycle notation for permutations.)

If $C(X,k)$ denotes the collection of $k$-subsets of $X$, then there is an induced action $G\curvearrowright C(X,k)$ given by $(g,A)\mapsto gA$ where $gA:=\{ga:a\in A\}$. The power set $\mathcal{P}(X)$ is the collection of all subsets of $X$, and it similarly carries an induced action.

A block system for $G\curvearrowright X$ is a set partition $\mathcal{B}$ of $X$ carrying an induced action of $G$. That is, for any part $B\in\mathcal{B}$ and element $g\in G$, the subset $gB=\{gb:b\in B\}$ is an element of the partition $\mathcal{B}$. In particular, either $gB=B$ or $gB\cap B=\varnothing$. In the example of the cube's symmetry group $G$ again, we can partition the vertex set $V$ into two substes according to whether vertices are adjacent or not (that is, according to the vertex sets of the two inscribed tetrahedra). This is a block system for $G\curvearrowright V$; every rotation $g$ either preserves the two tetrahedra's vertex sets, or switches them completely.

Also, I'm not sure what to call a 1-dimensional lattice of integers other than a quotient group

Some comments. The 1-dimensional lattice of integers we just call ... the integers. We don't call it a quotient group (unless in some other context it just so happens to arise as the quotient of some bigger group). What you're talking about is not the integers $\mathbb{Z}$, though, you are talking about quotients of the group of integers. These are finite cyclic groups, the integers mod $n$ denoted $\mathbb{Z}/n\mathbb{Z}$ or more compactly as $\mathbb{Z}_n$.

Given a group $G$, it acts on itself by "translation" (i.e. using the group's own binary operation as the map $G\times G\to G$). This is present in Cayley's theorem, for instance. In particular, a subgroup $H$ of $G$ acts on it, and the orbits are precisely the right cosets $Hg$. (Since your groups are abelian, there is no distinction between left coset $gH$ and right coset $Hg$). In particular, given an element $h$ of $G$, there is a cyclic subgroup $H=\langle h\rangle$. One way to build a block system for this action is to pick exactly one element from each coset, then form its orbit (in the induced action of $H$ on the collection of subsets of $X$).

So for instance, let's take $G=\mathbb{Z}/12\mathbb{Z}$. There is a cyclic subgroup $H=\{\bar{0},\bar{3},\bar{6},\bar{9}\}$ with cosets

$$ \begin{array}{l} \{\color{Red}{\bar{0}},\bar{3},\bar{6},\,\bar{9}\,\} \\ \{\color{Red}{\bar{1}},\bar{4},\bar{7},\bar{10}\} \\ \{\bar{2},\color{Red}{\bar{5}},\bar{8},\bar{11}\} \end{array} $$

The next step is to pick exactly one element of each coset, as done above in red. And finally, apply $H$ to the subset $\{\bar{0},\bar{1},\bar{5}\}$ to obtain

$$ \begin{array}{lllll} \bar{0} & + & \{\bar{0},\bar{1},\bar{5}\} & = & \{\bar{0},\bar{1},\bar{5}\} \\ \bar{3} & + & \{\bar{0},\bar{1},\bar{5}\} & = & \{\bar{3},\bar{4},\bar{8}\} & \\ \bar{6} & + & \{\bar{0},\bar{1},\bar{5}\} & = & \{\bar{6},\bar{7},\bar{11}\} \\ \bar{9} & + & \{\bar{0},\bar{1},\bar{5}\} & = & \{\bar{9},\bar{10},\bar{2}\} \end{array} $$