Artificial Wasteland · a rhythm that leaves no gap
No Beat Twice
Give several voices the same rhythm and let each start at a different moment. If you choose well, they strike every beat of the cycle exactly once: no beat doubled, no beat missed. Most rhythms cannot do it at all. Draw one below and this page will search, exhaustively, for the entry times that work.
The instrument
What the grid is showing
Write the beats of a cycle as the numbers 0, 1, 2, … n−1, and count
round: after n−1 comes 0 again. A rhythm is a set of those
numbers, the beats one voice strikes. Starting the same rhythm at beat b shifts
every onset by b.
So a canon is a piece of arithmetic. Take the set of onsets A and the set of entry
times B. Every beat of the cycle should be a + b for exactly one
choice of an onset a and an entry b. When that happens the two sets
are said to factor the cycle, and the grid above shows it directly: one row per voice,
one column per beat, and every column carries exactly one mark.
Because the strikes are all distinct and there are |A| × |B|
of them, the two sizes must multiply to n. That is the first thing the page checks,
and it is why a five-onset rhythm can never fill a twelve-beat cycle.
The other thing the page checks, before it searches at all
Turn a rhythm into a polynomial by writing x to the power of each onset and adding:
the rhythm {0, 1, 3} becomes 1 + x + x³. Then a factorisation of
the cycle says exactly that
A(x) B(x) = 1 + x + … + xn−1, once you agree that
xn means 1. The right hand side is a product of
cyclotomic polynomials, one for each divisor of n above one, and each
of those is irreducible, so each one has to divide A(x) or B(x).
That gives a test with no searching in it. If the cyclotomic polynomial belonging to a power of
a prime p divides a rhythm, then p divides the number of onsets: the
onsets fall into p equal groups. So when p does not divide the number
of voices, that cyclotomic polynomial has nowhere else to go and must divide the
rhythm. If it does not, no set of entry times can exist, and the page can say so without
trying any. The verdict panel names the obstruction when there is one.
The test is not complete. Some rhythms pass every cyclotomic condition of that kind and still have no complement, and for those the page falls back to exhaustive search over the placements. The search branches on which onset lands on the lowest uncovered beat, which is forced to be a single choice in any given factorisation, so it visits each factorisation exactly once and never twice.
How rare is it?
Rare, and it gets rarer in a strange, jumpy way that follows the arithmetic of
n rather than its size. Here is the complete count, for every cycle length we
could finish: how many rhythms tile at all, counted up to rotation, and how many
rhythm-and-entries pairs there are.
| beats | rhythms that tile | canons | with both patterns aperiodic |
|---|
Seventy-two
Look down the last column. Something is missing from all of it, and it stays missing for a long time.
A rhythm can be a shorter rhythm said twice. {0, 1, 6, 7} in a twelve-beat cycle
is just {0, 1} played at beats 0 and 6: shift it by six
and it lands on itself. Call such a pattern periodic. Periodic patterns are the easy
way to build a canon, and once you notice them you start to see that almost every canon has
one. If the rhythm repeats, the entries can be irregular; if the entries repeat, the rhythm can
be irregular. One side carries the regularity.
The question is whether both sides can be irregular at once, and the answer is that for small cycles they cannot. We checked every one. For every cycle length from two beats to seventy-one, every factorisation of the cycle has at least one periodic side. That is not a spot check: it is candidate rhythms examined, among which aperiodic rhythms genuinely do tile, and not one of them has an aperiodic partner.
At seventy-two beats it breaks.
These are called Vuza canons, after Dan Tudor Vuza, who worked out how to construct them in a four-part series in Perspectives of New Music between 1991 and 1993. He was chasing a musical object and rediscovered, on his own, a piece of group theory that had taken a generation of mathematicians: the cyclic groups in which every factorisation must have a periodic factor were classified between 1950 and 1957 by Hajos, Redei, de Bruijn and Sands, and 72 is the smallest order that is not one of them. What is above is not a quotation of that classification. We use it nowhere in the computation. It is the result of walking every factorisation and looking, and the classification is the reason we knew what we ought to find.
Which makes the agreement worth stating precisely, because agreeing with people who did this first is the only way to know the sweep is right. Our three rhythms and six partners are the same nine sets that Harald Fripertinger enumerated, and the same counts that Franck Jedrzejewski tabulates as three inner voices of six onsets against six outer voices of twelve. Sharper than the counts: for each of the nine we compute which cyclotomic polynomials divide it, and the two lists come out as for the rhythms and for the partners, which is divisor for divisor what Fripertinger prints. Sharper still: the worked examples that Jedrzejewski and Emmanuel Amiot print in their papers, three partners and two rhythms between them, all five land inside our nine classes. We computed ours first and compared afterwards.
The eighteen canons of 72 beats
Play one and then solo a single voice. Alone it sounds like nothing in particular, six strikes scattered over seventy-two beats with no pulse you can hold on to. Together, twelve of them, the beat is perfectly even and no two voices ever collide. Neither the rhythm nor the pattern of entries has any period at all. Nothing in the piece repeats, and nothing is missed.
What else the sweep at 72 found
Seventy-two can be split as six onsets in twelve voices, or eight in nine, or nine in eight, and so on. Only the six-and-twelve split yields anything. The eight-and-nine split is the interesting near miss: aperiodic rhythms of eight onsets do tile the seventy-two-beat cycle, which is far more than the six-onset rhythms that work, and every last one of them forces its nine entry times into a repeating pattern. The reason is visible in the algebra. With nine voices, no power of two can divide the entry set, so every one of the cyclotomic factors belonging to 2, 4 and 8 has to sit in the rhythm, and a rhythm carrying all three has exactly one onset in each residue class modulo eight. That is a strong enough grip to force the other side to repeat.
Where it stops being known
The cyclotomic conditions above are the beginning of a program that is still unfinished. In 1999 Ethan Coven and Aaron Meyerowitz isolated two conditions on a set of onsets, usually written (T1) and (T2). (T1) says the number of onsets equals the product of the primes belonging to the prime-power cyclotomic factors the rhythm carries. (T2) says that when you take several of those prime powers with distinct primes and multiply them together, the cyclotomic polynomial of the product divides the rhythm too. They proved that (T1) and (T2) together are enough: any set satisfying both tiles. And they proved that (T1) alone is necessary. Whether (T2) is necessary, in general, is open.
It is still open now. Izabella Laba and Itay Londner, who have moved the frontier further than anyone since, write in a paper accepted in July of this year that determining whether the conditions hold for all finite tiles is the main open problem concerning integer tilings. A rhythm that tiled while failing (T2) would settle it, in the direction nobody expects.
So we looked, and the looking is worth reporting exactly, including the part that makes it weak. Every rhythm you can draw here is decided by search rather than by the conditions, so nothing on this page rests on the conjecture. Across every cycle length whose census we could finish, rhythms tile, and every one of them satisfies both (T1) and (T2). That is worth almost nothing as evidence, and here is why: (T2) is a theorem, not a conjecture, whenever the number of onsets has at most two distinct prime factors, and of those rhythms have a size with three. The whole sweep sits inside the region where the answer was already known.
Inside seventy-two beats there is exactly one place where it is not known. A size with three distinct primes must be at least 30, and 30 onsets need at least 60 beats, so the unproved region within reach is a single family: thirty onsets, sixty beats, two voices. Those have a closed form, and we walked rotation classes of them. None fails (T2). That is a genuine look at the open question and it is also a very small one, over a family with a great deal of structure, which is not where a counterexample would be expected to hide.
The instrument reports both conditions for whatever you have drawn, so you can look too. Draw something with thirty onsets in sixty beats and you are in the unproved region.
A disagreement in the literature we could not settle
One more open thing, and it is not ours. Two published exhaustive classifications of the 144-beat cycle report the same class counts but pair them up differently, and so disagree on how many Vuza canons 144 has: Amiot's table yields and Jedrzejewski's yields . At most one can be right. Settling it needs a sweep of 144 beats, which is far past what the method here reaches, and we did not attempt it. It is the obvious next thing for anyone with more compute than a night.
The check
Everything on this page is recomputed, twice, in two languages. The engine that decides
your rhythm, canons.mjs, is shipped byte-identical to the copy in
research/rhythmic-canons/ that the laboratory ran; the verifier asserts the two
files hash the same. The large sweeps were run by census.c, a separate program
sharing no code with it, and the two agree exactly on every cycle length where both can run.
What is exhaustive: the statement that no cycle shorter than 72 beats has a canon with two aperiodic sides. Every subset that could be the smaller side of a factorisation was generated and tested, for every length from 2 to 71.
What is not: the count of all factorisations stops being computable partway up the
table, because a single rhythm can have astronomically many partners. The rhythm
{0, 27} in a 54-beat cycle has 226 of them. Rows past that point are
left blank rather than estimated.
One shortcut, and it is a proof, not a guess: the sweep at 72 skips rhythms that cannot possibly tile, using the cyclotomic argument described above. The same sweep was also run with the shortcut switched off, over all 1,342,970,325 candidate rhythms, and returned the same eighteen canons.
Against the literature: the nine sets at 72 beats match Fripertinger's and Jedrzejewski's published enumerations, in counts and divisor for divisor in their cyclotomic factors, and every worked example either author prints falls inside them. A caution for anyone checking us: these papers call the twelve-onset set the motif, so Fripertinger's phrase 6 motifs and 3 complements is our 6 partners and 3 rhythms, not the other way round. Reading it the natural way puts the 6 next to the six-onset rhythm and gets it wrong.
Not in the catalogue: the census columns above appear to be new. We searched OEIS for the counts of rhythms that tile and of canons, in several windows, and found nothing; the same query form returns the Fibonacci numbers and A102562, the non-Hajos orders, so the search was looking. The absence is a finding about the catalogue, not a claim of importance.
checks:
node research/rhythmic-canons/verify.mjs
Sources and honest edges
- D. T. Vuza, Supplementary Sets and Regular Complementary Unending Canons, Perspectives of New Music, four parts, 1991 to 1993. The construction that produces canons with two aperiodic sides.
- E. M. Coven and A. Meyerowitz, Tiling the integers with translates of one finite set, Journal of Algebra 212 (1999), 161 to 174. The conditions (T1) and (T2).
- H. Fripertinger, Enumeration of Vuza canons, the tables against which our count at 72 and the structure of its cyclotomic split were compared.
- F. Jedrzejewski, On the Enumeration of Vuza Canons, arXiv:1304.6609. Its Table 1 gives 72 as three inner voices of six onsets against six outer voices of twelve, and it is the source that attributes each part of the classification to the person who proved it.
- E. Amiot, Structures, Algorithms and Algebraic Tools for Rhythmic Canons, Perspectives of New Music 49(2), 2011, and New Perspectives on Rhythmic Canons and the Spectral Conjecture, Journal of Mathematics and Music 3(2), 2009. Worked examples we checked against, and the observation that 72 collapses to two canons up to affine equivalence rather than eighteen up to rotation.
- I. Laba and I. Londner, The Coven-Meyerowitz tiling conditions for 3 prime factors: the even case, accepted 2026, for the current status of the conjecture in the authors' own words.
- The classification of the cyclic groups in which every factorisation has a periodic factor was assembled between 1950 and 1957 by Hajos, Redei, de Bruijn and Sands. We use it nowhere in the computation; it is quoted only to say what our sweep was expected to find. The non-Hajos orders are OEIS A102562, beginning 72, 108, 120, 144.
Free choices worth naming. Factors are counted up to rotation of each side independently, which is the convention that makes a canon a canon rather than a particular performance of one; other papers count up to affine equivalence and get smaller numbers. A canon here is an ordered pair, a rhythm and a set of entries, so a canon and its dual are two. The audio assigns pitches to voices for legibility; the pitches are not part of the mathematics.