EP46

EP46: Rhythmic Canons & Tiling

Perfect Tiling of ℤₙ, Hajós Conjecture, and Vuza Canons

Abstract AlgebraCombinatoricsMusicology

前置知识

Overview / 概述

Four drummers take turns striking beats. Each beat is covered by exactly one player — zero overlap, zero gap. This is, in precise mathematical language, a perfect tiling of the cyclic group ℤₙ.

中文: “四个鼓手轮流打拍子。每一拍，恰好一个人覆盖。零重叠，零空隙。这在数学上，叫做循环群的完美铺砌。”

Take the integers modulo $n$ , the group $\mathbb{Z}_n = \{0, 1, \ldots, n-1\}$ under addition mod $n$ . Two subsets $A$ and $B$ tile the group when every element of $\mathbb{Z}_n$ can be written uniquely as a sum $a + b$ with $a \in A$ and $b \in B$ . The set $A$ provides the rhythmic pattern (which beats within a short cell to strike), and $B$ provides the starting offsets (when each voice enters). Together they pack the timeline perfectly.

The deep question is: when must one of $A$ or $B$ be periodic — that is, built from cosets of a proper subgroup? György Hajós conjectured in 1941 that the answer is always. N. Sands disproved this in 1974 with a counterexample in $\mathbb{Z}_{72}$ . Dan Tudor Vuza then systematically characterized all such aperiodic perfect tilings in 1991, producing what music theorists now call Vuza canons: polyphonic compositions where each voice’s individual pattern sounds irregular, but together they fill every beat exactly once.

中文: “同一个整数模 n 群，第四集排列音高，今天铺砌节奏。代数结构不在乎你往里面装的是什么。它只在乎元素之间的关系。”

Prerequisites / 前置知识

All-Interval Rows and ℤ₁₂ (EP04) — the cyclic group $\mathbb{Z}_{12}$ and its subgroup structure underlie all the tiling examples here; the same algebraic object that organizes pitch classes also organizes beat positions.

Definitions

Definition 46.1 (Cyclic Group ℤₙ)

The cyclic group $\mathbb{Z}_n$ is the set $\{0, 1, 2, \ldots, n-1\}$ equipped with addition modulo $n$ : $a \oplus b := (a + b) \bmod n.$ It has a unique subgroup of order $d$ for every divisor $d$ of $n$ , namely $H_d = \{0, d, 2d, \ldots, n-d\}$ .

Worked example. $\mathbb{Z}_{12} = \{0,1,\ldots,11\}$ has subgroups of orders $1, 2, 3, 4, 6, 12$ . The subgroup of order 4 is $\{0, 3, 6, 9\}$ . The subgroup of order 3 is $\{0, 4, 8\}$ . In EP04 the elements of $\mathbb{Z}_{12}$ label pitch classes; here they label beat positions in a 12-beat cycle.

Definition 46.2 (Perfect Tiling (Direct-Sum Factorization))

Two non-empty subsets $A, B \subseteq \mathbb{Z}_n$ form a perfect tiling of $\mathbb{Z}_n$ , written $A \oplus B = \mathbb{Z}_n$ , if every element $x \in \mathbb{Z}_n$ has a unique representation $x = a + b \pmod{n}, \quad a \in A, \; b \in B.$ Equivalently: (i) every element of $\mathbb{Z}_n$ is covered ( $A + B = \mathbb{Z}_n$ ) and (ii) no element is covered twice ( $|A| \cdot |B| = n$ and all sums are distinct). The notation $\oplus$ emphasizes that the sum is direct.

Necessary condition. $|A| \cdot |B| = n$ .

Worked example. Take $n = 12$ , $A = \{0, 3, 6, 9\}$ , $B = \{0, 1, 2\}$ . Then $|A| \cdot |B| = 4 \times 3 = 12$ . Computing all sums: translating $B$ by each element of $A$ gives $\{0,1,2\}$ , $\{3,4,5\}$ , $\{6,7,8\}$ , $\{9,10,11\}$ — four disjoint blocks covering all 12 positions. Hence $\{0,3,6,9\} \oplus \{0,1,2\} = \mathbb{Z}_{12}$ .

Musical reading. $A$ is the rhythmic pattern (which beats to strike within one pass), and $B$ is the set of starting offsets for different voices. The canon has four voices entering at offsets 0, 3, 6, 9, each playing the pattern $\{0,1,2\}$ within its window — together covering every beat exactly once.

Definition 46.3 (Periodic Subset (Coset Union))

A subset $S \subseteq \mathbb{Z}_n$ is periodic if there exists a proper subgroup $H < \mathbb{Z}_n$ (i.e., $H \neq \{0\}$ and $H \neq \mathbb{Z}_n$ ) such that $S$ is a union of cosets of $H$ : $S = \bigcup_{i \in I} (s_i + H), \quad s_i \in \mathbb{Z}_n.$ Equivalently, $S + H = S$ ( $S$ is $H$ -invariant under translation). The subset is aperiodic if no such proper subgroup $H$ exists.

Worked example. In $\mathbb{Z}_{12}$ , the set $A = \{0,3,6,9\}$ is periodic: it is the unique subgroup of order 4, so it is its own coset $0 + H_3$ (where $H_3 = \{0,3,6,9\}$ ). By contrast, $B = \{0,1,2\}$ is aperiodic — no proper subgroup of $\mathbb{Z}_{12}$ is a subset of $\{0,1,2\}$ other than $\{0\}$ , and $\{0,1,2\}$ is not a union of cosets of any proper subgroup of order > 1.

Definition 46.4 (Vuza Canon)

A Vuza canon is a perfect tiling $A \oplus B = \mathbb{Z}_n$ where both $A$ and $B$ are aperiodic (Definition 46.3). That is, neither subset is the union of cosets of any proper subgroup of $\mathbb{Z}_n$ .

The minimum value of $n$ for which a Vuza canon exists is $n = 72$ . All admissible values of $n$ are non-zero multiples of at least one of the following: 72, 108, 120, 144, …

Musical interpretation. Each voice’s rhythmic pattern (represented by $A$ ) sounds irregular and patternless in isolation. The set of entry points ( $B$ ) is equally irregular. Yet superimposed, the canon fills the entire $n$ -beat cycle with exactly one hit per beat.

Main Theorems / 主要定理

Theorem 46.1 (Hajós Conjecture (1941) — Statement)

(Hajós’s original conjecture, stated as a theorem about its own content.) Every perfect tiling $A \oplus B = \mathbb{Z}_n$ satisfies: at least one of $A$ or $B$ is periodic (a union of cosets of a proper subgroup of $\mathbb{Z}_n$ ).

Status: FALSE. The conjecture was disproved by N. Sands (1974).

Proof.

We prove the conjecture is false by exhibiting a counterexample. In

\mathbb{Z}_{72}

, Sands constructed explicit subsets

A

and

B

with

A \oplus B = \mathbb{Z}_{72}

such that neither

A

nor

B

is periodic. The existence of such a pair (a Vuza canon) refutes the conjecture: since both factors are aperiodic, the “at least one is periodic” conclusion fails. The precise construction of Sands’s sets is given in Theorem 46.2; verifying

A \oplus B = \mathbb{Z}_{72}

and aperiodicity of both factors constitutes the complete disproof.

\square

Theorem 46.2 (Perfect Tiling via the Polynomial (Mask) Method)

Let

A \subseteq \mathbb{Z}_n

and define its mask polynomial

A(X) = \sum_{a \in A} X^a \in \mathbb{Z}[X] / (X^n - 1).

Then

A \oplus B = \mathbb{Z}_n

if and only if

A(X) \cdot B(X) \equiv 1 + X + X^2 + \cdots + X^{n-1} \pmod{X^n - 1}.

Proof.

The right-hand side is the mask polynomial of $\mathbb{Z}_n$ itself (every element appears once). The product $A(X) \cdot B(X)$ collects, for each power $X^k$ , the number of ways to write $k \equiv a + b \pmod{n}$ with $a \in A$ , $b \in B$ . The product equals the all-ones polynomial mod $X^n - 1$ if and only if every residue $k$ occurs exactly once — which is precisely the definition of a perfect tiling. This algebraic criterion reduces tiling verification to polynomial arithmetic and enables both construction and classification of tilings via factorization in $\mathbb{Z}[X]/(X^n-1)$ . $\square$

Worked example. For $n=12$ , $A=\{0,3,6,9\}$ , $B=\{0,1,2\}$ : $A(X) = 1 + X^3 + X^6 + X^9, \quad B(X) = 1 + X + X^2.$ $A(X) \cdot B(X) = (1+X^3+X^6+X^9)(1+X+X^2) = 1+X+X^2+X^3+\cdots+X^{11} \pmod{X^{12}-1}. \quad \checkmark$

Theorem 46.3 (Vuza Canon Construction via Subgroup Chains)

Let

n

be a positive integer admitting a Vuza canon. Then there exists a chain of subgroups

\mathbb{Z}_n \supset H_1 \supset H_2 \supset \cdots \supset H_k = \{0\}

and coset representative sets

R_1, R_2, \ldots, R_k

chosen from successive quotient groups such that

A = R_1 + R_2 + \cdots + R_j, \quad B = R_{j+1} + \cdots + R_k

form a perfect tiling

A \oplus B = \mathbb{Z}_n

with both

A

and

B

aperiodic. The smallest such

n

n = 72

Proof.

The key idea is the subgroup chain factorization. Because

72 = 4 \cdot 3 \cdot 6

(and 72 is divisible by 4, 12, and 36), one may find a chain

\mathbb{Z}_{72} \supset \mathbb{Z}_{36} \supset \mathbb{Z}_{12} \supset \mathbb{Z}_4

. At each level, one selects coset representatives in the quotient group. The critical point: at each level, representatives can be chosen to avoid creating periodicity in the assembled set. The aperiodicity of

A

and

B

is verified by checking that neither set is stabilized by any non-trivial subgroup of

\mathbb{Z}_{72}

. Perfect tiling follows from the fact that the successive coset decompositions partition

\mathbb{Z}_{72}

completely at each step, and the overall product of mask polynomials equals

1 + X + \cdots + X^{71}

mod

X^{72} - 1

. The minimality of

n = 72

was established by exhaustive checking for smaller

n

: all integers

n < 72

satisfying the necessary divisibility conditions admit only periodic tilings.

\square

Theorem 46.4 (Coven–Meyerowitz T1 and T2 Conditions)

(Coven & Meyerowitz, 1999.) Define the following two conditions on a finite set $A \subseteq \mathbb{Z}$ :

T1: For every prime $p$ dividing $|A|$ , the cyclotomic polynomial $\Phi_p(X)$ divides the mask polynomial $A(X)$ in $\mathbb{Z}[X]$ .
T2: For primes $p \neq q$ both dividing $|A|$ , $\Phi_{pq}(X)$ does NOT divide $A(X)$ .

Then:

(T1 is necessary): If $A$ tiles $\mathbb{Z}$ (by translation), then $A$ satisfies T1.
(T1 + T2 is sufficient): If $A$ satisfies both T1 and T2, then $A$ tiles $\mathbb{Z}$ .
(Open problem): Whether T1 alone is sufficient remains unknown.

Proof.

The necessity of T1 follows from a spectral argument: if $A \oplus B = \mathbb{Z}_n$ , then for every primitive $n$ -th root of unity $\omega^k$ , we have $A(\omega^k) \cdot B(\omega^k) = 0$ (since the all-ones polynomial vanishes at all non-trivial roots of unity). Each prime $p$ dividing $|A|$ forces zeros of $A(X)$ at the primitive $p$ -th roots of unity — which is exactly divisibility by $\Phi_p(X)$ .

The sufficiency of T1 + T2 is proved by induction on $|A|$ : the T2 condition ensures that the factorization $A(X) \cdot B(X) = 1 + X + \cdots + X^{n-1}$ can be assembled step by step without cyclotomic collisions. Whether T1 alone suffices — i.e., whether there exists a T1-satisfying set that does not tile — remains an open problem as of 2024. $\square$

Numerical Examples

Example 1: Two tilings of ℤ₁₂

Tiling A: $A = \{0,3,6,9\}$ , $B = \{0,1,2\}$ , so $|A| \times |B| = 4 \times 3 = 12$ .

The four translates of $B$ by elements of $A$ :

Voice	Entry offset (from A)	Beats covered (B + offset)
1	0	{0, 1, 2}
2	3	{3, 4, 5}
3	6	{6, 7, 8}
4	9	{9, 10, 11}

Total coverage: $\{0,1,2,3,4,5,6,7,8,9,10,11\} = \mathbb{Z}_{12}$ . No overlaps. ✓

Tiling B: $A' = \{0,2,4,6,8,10\}$ , $B' = \{0,1\}$ , so $|A'| \times |B'| = 6 \times 2 = 12$ .

Here $A'$ is the even-indexed subgroup of $\mathbb{Z}_{12}$ (periodic), and $B'$ is the set $\{0,1\}$ (aperiodic). Six voices enter on even beats; each voice strikes two consecutive positions.

Both tilings satisfy $A \oplus B = \mathbb{Z}_{12}$ , but neither is a Vuza canon: in Tiling A, the factor $A = \{0,3,6,9\}$ is periodic (it is the order-4 subgroup); in Tiling B, $A'$ is periodic.

Example 2: Smallest Vuza canon modulus

The minimal $n$ admitting a Vuza canon is $n = 72$ . The sequence of admissible moduli begins:

n \in \{72, 108, 120, 144, \ldots\}

All admissible $n$ are non- $p$ -group multiples with at least three distinct prime factors in their factorization in the requisite form.

Example 3: Polynomial check for Z₁₂ Tiling A

A(X) \cdot B(X) = (1 + X^3 + X^6 + X^9)(1 + X + X^2)

Expanding and reducing mod $X^{12} - 1$ :

= 1 + X + X^2 + X^3 + X^4 + X^5 + X^6 + X^7 + X^8 + X^9 + X^{10} + X^{11}

This equals the mask polynomial of $\mathbb{Z}_{12}$ , confirming the tiling.

Musical Connection / 音乐联系

音乐联系

Rhythmic Canons as Perfect Tilings

The mathematical framework of this episode has a direct compositional interpretation. A rhythmic canon is a piece where the same rhythmic cell $A$ is played by multiple voices, each entering at a different offset given by $B$ . If $A \oplus B = \mathbb{Z}_n$ , the canon is perfect: at every beat position, exactly one voice strikes.

The connection to

EP04 (ℤ₁₂ and pitch-class sets)

is not superficial: the same algebraic object — the cyclic group $\mathbb{Z}_n$ — organizes both pitch classes (with $n = 12$ ) and rhythmic positions (with $n$ equal to the period length). An all-interval row in EP04 is a permutation of $\mathbb{Z}_{12}$ exhausting all intervals; a perfect rhythmic tiling exhausts all beat positions.

中文: “这里的整数模十二群，和第四集排列音高用的是同一个代数对象。装音高是十二音序列，装节拍就是节奏卡农。”

Messiaen’s Non-Retrogradable Rhythms

Olivier Messiaen developed what he called non-retrogradable rhythms: rhythmic patterns that read the same forwards and backwards. The canonical example is the duration sequence 3, 2, 1, 2, 3 — a palindrome. Messiaen regarded these as possessing an intrinsic symmetry that gave them a “frozen” or timeless quality in his compositions (Quartet for the End of Time, 1941).

The relationship to tiling theory is instructive precisely because it is a contrast, not a connection. A palindromic rhythm has a reflective symmetry ( $s \mapsto -s \pmod n$ ) but this does not imply it tiles. Conversely, a Vuza canon has no internal symmetry whatsoever — both $A$ and $B$ are aperiodic, with no rotational or reflective structure — yet together they achieve a global perfection. Symmetry and tiling are orthogonal properties: symmetric rhythms need not tile; aperiodic tiles need not be symmetric.

中文: “梅西安的回文节奏满足正读逆读相同，在循环群上具有内在对称性——这与铺砌理论在非周期性条件上有深层联系，但回文节奏本身并不直接构成铺砌，而是一个对照案例：对称性未必产生铺砌，铺砌也未必具有对称性。”

Compositional implications of Vuza canons

From a composer’s perspective, Vuza canons present a paradox. Each voice, heard in isolation, sounds unpredictable and irregular — the pattern $A$ in $\mathbb{Z}_{72}$ has no internal period shorter than 72 beats. The entries $B$ are equally irregular. Yet the ensemble produces a texture of perfect regularity: every beat sounds exactly once. This is the rhythmic analogue of an aperiodic tiling of the plane (Penrose tilings) — local disorder, global order.

The applications extend beyond pure composition: tiling sequences appear in error-correcting codes (cyclic codes), frequency-hopping spread spectrum communications (where aperiodic patterns reduce interference while maintaining total coverage), and crystallography (aperiodic but complete lattice tilings).

Limits and Open Questions / 局限性与开放问题

Coven–Meyerowitz completeness. The T1 condition is known to be necessary for tiling. T1 + T2 together are sufficient. The central open problem is whether T1 alone is sufficient — i.e., whether T2 can be deduced from T1 or whether there exist T1-satisfying sets that do not tile.
Classification of Vuza canon moduli. The exact characterization of all integers $n$ that admit Vuza canons is still incomplete. Known admissible values include 72, 108, 120, 144, and more; the arithmetic conditions necessary and sufficient for admissibility are not fully understood for large $n$ .
Higher-dimensional tiling. The current theory focuses on tilings of $\mathbb{Z}_n$ (one-dimensional). Tilings of $\mathbb{Z}^d$ for $d \geq 2$ (two- and three-dimensional rhythmic structures, polyrhythm grids) raise different and largely open classification problems.
Computational recognition. Given a pair $(A, B)$ with $A \oplus B = \mathbb{Z}_n$ , deciding whether the tiling is a Vuza canon (both factors aperiodic) is straightforward. But the inverse problem — given $n$ , enumerate all Vuza canons up to translation — is computationally intensive and not fully solved for large $n$ .
Spectral vs. combinatorial methods. The Coven–Meyerowitz approach uses cyclotomic polynomial divisibility (spectral/algebraic). An alternative approach uses the spectral set conjecture (Fuglede 1974, now known to be false in dimension $\geq 3$ but open in dimensions 1 and 2 for $\mathbb{Z}_n$ ): a set tiles by translation if and only if it is a spectral set (its $L^2$ space admits an orthonormal basis of exponentials). The precise relationship between tiling and spectrality in $\mathbb{Z}_n$ remains active research.

Conjecture (Coven–Meyerowitz T1 Sufficiency)

Every finite set $A \subseteq \mathbb{Z}$ satisfying condition T1 (the cyclotomic polynomial $\Phi_p(X)$ divides $A(X)$ in $\mathbb{Z}[X]$ for every prime $p$ dividing $|A|$ ) also tiles $\mathbb{Z}$ by translation — i.e., there exists a set $B$ such that $A \oplus B = \mathbb{Z}_n$ for some $n$ .

Falsification criterion: Exhibit a finite set $A$ satisfying T1 and prove that no set $B$ tiles with it. A counterexample would require showing that the polynomial $(1 + X + \cdots + X^{n-1}) / A(X)$ — even though divisible-by- $\Phi_p$ for each prime factor — does not correspond to any valid subset $B \subseteq \{0,\ldots,n-1\}$ with non-negative integer coefficients. No such counterexample is known as of 2024.

Conjecture (Fuglede Spectral-Tiling Equivalence in ℤₙ)

A subset $A \subseteq \mathbb{Z}_n$ tiles $\mathbb{Z}_n$ by translation if and only if $A$ is a spectral set: the Hilbert space $\ell^2(A)$ (functions on $A$ ) admits an orthonormal basis of characters of $\mathbb{Z}_n$ restricted to $A$ .

Falsification criterion: Find a tile $A$ in $\mathbb{Z}_n$ that is not a spectral set, or a spectral set that does not tile. In continuous $\mathbb{R}^d$ for $d \geq 3$ the conjecture is false (Tao 2004, Kolountzakis–Matolcsi 2006); in $\mathbb{Z}_n$ and in $\mathbb{R}^1, \mathbb{R}^2$ it remains open.

Academic References / 参考文献

Hajós, G. (1941). Über einfache und mehrfache Bedeckung des $n$ -dimensionalen Raumes mit einem Würfelgitter. Acta Mathematica Hungarica, 1(1), 1–6.
Sands, N. (1974). On the factorization of finite abelian groups. Acta Mathematica Hungarica, 25(3–4), 279–284.
Vuza, D. T. (1991–1992). Supplementary sets and regular complementary unending canons. Perspectives of New Music, 29(2), 22–49; 30(1), 184–207; 30(2), 102–125; 31(1), 270–305.
Coven, E. M., & Meyerowitz, A. (1999). Tiling the integers with translates of one finite set. Journal of Algebra, 212(1), 161–174.
Andreatta, M. (2003). On group-theoretical methods applied to music: Some compositional and implementational aspects. In Perspectives in Mathematical and Computational Music Theory. Universität Osnabrück, 169–193.
Jedrzejewski, F. (2006). Mathematical Theory of Music. Delatour France / IRCAM.
Kolountzakis, M. N., & Matolcsi, M. (2006). Tiles with no spectra. Forum Mathematicum, 18(3), 519–528.
Amiot, E. (2011). Structures, algorithms, and algebraic tools for rhythmic canons. Perspectives of New Music, 49(2), 93–143.
Tao, T. (2004). Fuglede’s conjecture is false in 5 and higher dimensions. Mathematical Research Letters, 11(2–3), 251–258.
Amiot, E. (2016). Music Through Fourier Space: Discrete Fourier Transform in Music Theory. Springer. Ch. 3–4.
Kolountzakis, M. N. (2000). The study of translational tiling with Fourier analysis. In Fourier Analysis and Convexity. Birkhäuser, 131–187.
Andreatta, M., & Agon, C. (2009). Tiling problems in music composition: Theory and implementation. In Proceedings of the International Computer Music Conference (ICMC 2009).
Fuglede, B. (1974). Commuting self-adjoint partial differential operators and a group theoretic problem. Journal of Functional Analysis, 16(1), 101–121.