Autosimilar Melodies
Autosimilar Melodies
Autosimilar Melodies
net/publication/243044150
Autosimilar melodies
CITATIONS READS
10 467
1 author:
Emmanuel Amiot
Université de Perpignan
65 PUBLICATIONS 339 CITATIONS
SEE PROFILE
Some of the authors of this publication are also working on these related projects:
All content following this page was uploaded by Emmanuel Amiot on 30 September 2014.
Emmanuel AMIOT
1 rue du Centre, F 66570 St NAZAIRE, France
(v1.0.0 released july 2007)
The present work surged from purely musical topics, namely the notion of ’selfRep melody’ as defined by composer Tom Johnson in [7],
and reaped interesting mathematical rewards as well as musical. It is about melodies that contain themselves in augmentation, and
some generalizations thereof. Some of the mathematical by-results are new to the best of the author’s knowledge. Applications range
from melodies to rhythms, and include some new results on mosaics. Finally, extension to approximate and ‘non invertible’ autosimilar
melodies will prove that this notion is both widespread and universal.
Notations: Zn stands for the cyclic set with n elements, considered as the group (Zn , +) or as a ring as
the occasion demands – or just a set.
We denote the greatest common divisor of a, n by gcd(a, n). Quite often, calculations make sense both in
Zn and Z. When in doubt, consider that a ∈ Zn can be identified with the smallest non negative integer
in Z with residue a.
Division is sometimes denoted by |: for instance 8 | 4 mod 12 as 4 = 5 × 8 mod 12.
The invertible elements of (Zn , ×) are the generators of the additive group (Zn , +); they form a multi-
plicative group, Z∗n .
Any set might be given by the list of its elements: (0, 3, 5); or by some defining property, e.g. Z∗n = {a ∈
Zn , gcd(a, n) = 1}.
The subgroup generated by some element g of a group G is denoted by gr(g). For instance gr(a) =
(Zn , +) ⇐⇒ a ∈ Z∗n .
A periodic melody M is a map from Zn into some musical space, usually pitches or notes, or equivalently
a periodic sequence: ∀k ∈ Z, Mk+n = Mk . So Mk is well defined for k ∈ Zn .
The affine group modulo n is Aff n , the set of affine bijections in Zn , i.e. x 7→ a x + b for (a, b) ∈ Z∗n × Zn .
The order of an element g of a group G is the cardinality of gr(g), i.e. the smallest integer r > 0 with
g r = e, the unit element of group G. It is classically characterized by the following equivalence:
g k = e ⇐⇒ o(g) is a divisor of k
Introduction
Symmetries of Zn have been well explored under the group of translations and inversion (T/I), for instance
in American Set Theory. Such transformations are expressed by maps x 7→ ±x + b. But despite the obvious
interest of more general affine transforms in Zn , e.g. x 7→ a x + b, very little research has been made on
orbits of affine maps, or subgroups of the affine group1 . This is mildly surprising, as many interesting
notions are invariant under affine transformations: interval content (up to permutation), all-interval sets,
limited transposition modes2 , tiling (mosaic) property, series and all-interval series, to name but a few.
The present paper is on the one hand a mathematical study of orbits of affine maps operating on a
cyclic group. On the other hand it is developing a musically interesting notion of autosimilarity, just like
famous fractals (the Cantor Set, Koch flake, Sierpinski sponge) but discrete. Diverse musical renderings are
possible; in the simplest a melody plays within itself contrapunctically, something the Cantor of Leipzig
might have dreamed of. Several instances of such melodies have been identified in classical music.
We begin with the simplest case, when all augmentations begin on the same note. This is historically the
case studied by Tom Johnson in [7], though he came across the more general case, with different starting
points, which will be studied in section III; other generalizations will occur in the last sections.
∀k ∈ Zn M a k = Mk
This means that taking one note every a beats lets hear the same melody, only slower; or equivalently
that some augmentation of the melody is part of the melody itself, as is quite obvious on the score below
(with a = 3). This explains why the melody has to be infinite. Non-periodic solutions are possible2 , but
this would be another subject.
1 We decided to change Tom Johnson’s ‘selfRep’ to ‘autoSimilar’, that he himself used in the broad sense of ‘product of some iterated
process’, because it is really the traditional mathematical meaning, for instance with classical fractals.
2 like motif xx enlarged, e.g. . . . dcbaabcd. . . obtained from aa, b..b, c....c and so on.
GGGE[ 3
Of course, use of augmentation is quite ancient. J.S. Bach is probably the best known exponent of
melodies played simultaneously with their augmentations in numerous fugas; he is also famous for having
several voices heard inside one monody (Suites for solo strings spring to mind), but we haven’t found yet
striking examples of his using both ideas at the same time. Tom Johnson has discovered this possibility
around 1980, and is probably the first composer who made use of it conscioulsly and extensively, as in la
Vie Est Si Courte above, or Loops for Orchestra below, fig. 18.
But his works are by no means the earliest featuring autosimilar melodies: another famous american
piece where the melody is autosimilar (with ratio 4) is Glen Miller’s In the Mood. This is perfectly audible
as the extraction of one note out of four coincides with strong beats, and probably quite voluntary on
Miller’s part as he studied with the mathematically minded (some say ‘obsessed’) Joseph Schillinger1 .
But it might surprise many readers to realise that much more ancient western music features autosimi-
larity: it is found in Beethoven’s Fifth Symphony, arguably unconsciously as the ratio 3 autosimilarity is
not outlined (fig. 5); or, more interestingly, the ubiquitous Alberti Bass, well known from for instance the
beginning of Mozart’s Sonata in C major K. 545, is an excellent example, with autosimilarities at ratios
3, 5 and generally every odd number. In Mozart’s first bar, the right hand significantly offers a choice of
the three notes repeated by the left hand, at a ratio approximating 3 (three notes for eight beats).
Theorem 1.2 Any autosimilar melody with ratio a and period n is built up from orbits of the affine map
x 7→ a × x mod n: if the orbit of x is defined as
then for each note p of the melody, the subset of indexes M −1 (p) = {i ∈ Zn , Mi = p} is one such orbit, or
an union of several ones.
Proof It is sufficient to prove that if Mx = p then Mk = p for all k ∈ Ox , hence every orbit will come in
toto for a given note. But this is obvious from the definition, as
Mk = Mam ×x = Mam−1 ×x = . . . Mx = p
1 This was pointed out by T. Johnson. Almost forgotten nowadays, Schillinger taught a number of prominent composers before WWII.
To quote Henry Cowell in the preface of his book on Schillinger, “The idea behind the Schillinger System is simple and inevitable: it
undertakes the application of mathematical logic to all the materials of music and to their functions, so that the student may know the
unifying principles behind these functions, may grasp the method of analyzing and synthesizing any musical materials that he may find
anywhere or may discover for himself, and may perceive how to develop new materials as he feels the need for them.”
4 autosimilar melodies
A well known fact about orbits is worth recalling here, namely that x ∈ Oy ⇐⇒ y ∈ Ox .
In group theory, these orbits are the classes of the action of the cyclic subgroup generated by the map
f : x 7→ ax mod n.
At this point it seems a good idea to demand that a (or f ) indeed generates a subgroup, which means
that a is coprime with n or equivalently a ∈ Z∗n . As will be seen below, interesting situations arise when
this condition is dropped, but this will not happen before section V. So from now on,
The ratio of an autosimilar melody is assumed to be coprime with the period.
Example 1.3 The abstract melody generated by ratio 3 modulo 8 has five orbits: 0 is sent to 0 so (0)
is one orbit. 1 is sent to 3 and 3 sent to 1, so (1 3) is another one. (4), (5 7), (2 6) are the remaining
orbits, hence the general structure, x, y . . . denoting arbitrary pitches, is:
x y z y t u z u...
0 1 2 3 4 5 6 7...
The Alberti Bass (cf. fig. 3) has less than five notes. This comes from using the same note for different
orbits: putting arbitrarily (more about this later) C on 0 and 4, G on odd beats i.e. (1 3) and (5 7), and
E on (2 6) we have it, autosimilar with ratio 3: C G E G C G E G C G . . .
Here several orbits have been collapsed on identical notes: z = E, x = t = C, u = y = G. Hence it is
necessary to define:
Definition 1.4 A primitive autosimilar melody is a melody generated by a ratio a and a modulo n with
different notes for different orbits. In other words, there as many different notes as possible for the given
n, a.
As will be seen below, several mathematical results will only stand for primitive melodies: obviously
the possibility of collapsing all the orbits into as little as one (a one note melody, or even a melody of
silences. . . like Cage’s 4’33” !) hurts any attempt at a classification of symmetries.
Proof The orbit of 1 is exactly the subgroup of Zn ∗ generated by a, e.g. all different powers of a mod n:
hence ]O1 = o(a).
Let x 6= 0, now the map y 7→ y × x is one-to-one (as x must be invertible, Zn being a field when n is
prime) and maps precisely O1 onto Ox : hence |Ox | = |O1 | = o(a).
n−1
This is the only case where the number of different notes in the melody is easily computed, i.e. 1+ .
o(a)
Musically it is a natural idea to put a rest (or silence) on the singleton 0; so does Tom Johnson in many
instances. The result above also proves that such autosimilar melodies are instances of tilings, or mosaics,
with augmentation: the tile O1 will tile the line (e.g. Z) with its augmentations x1 O1 , x2 O1 . . . , leaving
aside only the multiples of n. An example will clarify this: let n = 7 and choose a ∈ Zn with order less
than n − 1, e.g. a = 2: then the orbit of 1 modulo 7 is (1, 2, 4) and the last orbit O2 is (3, 6, 12) which
GGGE[ 5
reduces modulo 7 to (3, 5, 6). Leaving the reduction aside enables to hear the augmentation, like in the
following musical rendering (fig. 4 was done in OpenMusic) of this canon con augmentatio:
In the intermediate case of x 7→ a x mod n, we can give a few explicit formulas. As will be proved in the
next section, these formulas will still be effective about half of the time in the most general case.
1.5.1 Number of occurences of one note. Some special cases are easy: O0 always has a single element,
and O1 is the multiplicative subgroup generated by a, i.e. the set of powers of a, and its cardinality is
equal to the order o(a) of a. This is exactly what happened for n prime.
The group Z∗n however, though abelian, is fairly complicated. In particular, the maximal order of any
element a ∈ Z∗n , that is to say the largest possible number of occurences of one note in a n−periodic
primitive autosimilar melody, is given by Carmichael’s Λ function1 . Also, even for simple a’s, for instance
for a = p prime, the lenghts of orbits are by no mean easy to compute2 . This hinges on a new behaviour:
contrariwise to the n prime case, the map
t7→x×t
O1 3 ak −→ x × ak ∈ Ox
Ψx :Z → Ox
k 7→ ak x mod n
o(a) is a period of Ψx , meaning that Ψx (k + o(a)) = Ψx (k) for all k ∈ Z. Now the set of all periods of
any map, here
T (Ψx ) = {τ ∈ Z, ∀k ∈ Z, Ψx (k + τ ) = Ψx (k)
is an additive group. But subgroups of Z are monogenous: T (Ψx ) = r Z. As o(a) ∈ T (Ψx ) we get that r
divides o(a), and r, smallest period of Ψx , is clearly the length of Ox (in short, f acts on Ox as a circular
permutation).
It is useful to visualise all this orbits as little clocks of different sizes, ticking at different speeds, with
at least one great clock whose size is a multiple of all others. Each multiplication by a mod n ticks every
clock, and after a whole ‘day’, e.g. after o(a) ticks, all clocks must have resumed their initial positions.
This is the substance of the above proposition. The perception of an autosimilar melody is then explained
as an aural illusion: multiplying by a, i.e. picking one note every a beat, does completely rearrange the
order of all the notes inside, but as the different onsets of a given note belong to the same orbit, we believe
we hear the same note at the same moment.
1 5
7 3 11 2 13 10
0
12 6 16 4 17 20
14
8 19
1 The Carmichael function Λ verifies Λ(pα q β . . . ) = lcm[Λ(pα ), Λ(q β ), . . . ] with Λ(pα ) = Φ(pα ) = (p−1)pα−1 except when p = 2 < α.
See http://mathworld.wolfram.com/CarmichaelFunction.html for details.
2 The orbits (x, p x, p2 x . . . ) are called cyclotomic orbits, their lengths are the degrees of the irreducible factors of X n − 1 in the ring
of polynomials on the field with p elements, see [1] for a musical application to a species of rhythmic canons.
GGGE[ 7
This result looks a little unsatisfactory, as one would like to predict the length of the orbit of a given x.
A precise answer requires, not algebra, but arithmetics:
Proposition 1.8 Let d = gcd(x, n); the length of Ox = {x, a x, a2 x, . . . } is the order of a modulo n/d,
i.e. the smallest integer k > 0 with ak = 1 mod n/d. In particular, Ox is of maximal length whenever x
and n are coprime.
Proof The nicest way to see this is perhaps to see Ox as an orbit of the map y 7→ a y operating on x Zn , the
set of all multiples of x; but this subset is a cyclic group, precisely the subgroup generated by d = gcd(x, n)
in Zn , with n/d elements. Dividing by d all elements of the orbit yields the orbit of y = x/d in the cyclic
group Zn/d = Zm . As y = x/d is now coprime with m = n/d, it only remains to prove this special case:
Lemma 1.9 If gcd(y, m) = 1 then the length of the orbit of y in Zm is exactly the order of a modulo m.
Which is obvious by direct calculation: the orbit loops to its starting point when
as by assumption, y is invertible modulo m and hence simplifiable. More quickly, one could argue as above
that the map Ψy is one-to-one and maps O1 to Oy .
Example 1.10 Let n = 15, a = 2. Then o(a) = 4. One singleton orbit, O0 . As 1 and 7 are invertible, their
orbits have 4 elements each. So is O3 = (3, 6, 9, 12) though 3 is not invertible mod. 15. This is because
(2k − 1) 6= 0 mod 5 = 15/3 ∀ k < 4, hence the orbit still hits maximum size. But O5 has only 2 elements,
as (22 − 1) = 0 mod 15/5 = 3.
We draw the reader’s attention to the fact that the automorphisms of the additive group (Zn , +), which
are the x 7→ b x with b ∈ Zn ∗ , permute these maximal orbits. Indeed they permute all orbits, preserving
their sizes.
On the other hand, more general x 7→ b x with gcd(b, n) > 1 will not be one-to-one, but none the less
carry one orbit into (part of) another; the cases are manifold.
1.5.2 Number of single notes. A last particular case is that of one note orbits, aka single notes, aka
fixed points of the map x 7→ a x.
This means exactly that x contains the prime factors of n that are missing in a − 1. For instance, say a = 4
and n = 15: such x’s are simply the multiples of 5. Hence
Proposition 1.11 The number of single notes in a primitive autosimilar melody of ratio a and period n
is gcd(a − 1, n). They are the multiples of n/ gcd(a − 1, n).
This will come as a special case of Prop. 2.15.
Looking for an autosimilar melody with ratio 3 and period 8, we can thus predict gcd(3 − 1, 8) = 2
singletons, and indeed 0 and 4 are the only fixed points of the map x 7→ 3x mod 8 (both are note C in
the Mozart example). This result will be deeply extended in the following section.
Tom Johnson conjectured that the total number of different notes in a melody with period n is at most
3n/4, as indeed happens for the following melody (n = 8, a = 5, 6 different notes):
This is true, as the largest number of different notes is obviously achieved with as many one-note orbits
as possible, the rest being organized in two-notes orbits. But the greatest possible value of gcd(n, a − 1) is
n/2 and it happens for a − 1 = n/2. So n must be even, the fixed points being the even numbers as
a × 2x = (n + 2) × x = 2 x mod n
8 autosimilar melodies
and this will yield two-notes orbits whenever this result is still odd, i.e. when n/2 is even. Hence
Proposition 1.12 The maximal number of different orbits is 3n/4. It is achieved when n = 4k, a = 2k+1.
The more general case, especially from an aural point of view, is the action of any affine automorphism.
Practically, the following definition means that by extracting one note every a notes in the melody, one
hears the same melody, though perhaps with a different starting point (namely b) – but this is surely
irrelevant mathematically, as periodic melodies do not have a starting point (musically this is a different
story of course, what with strong and weak beats, orchestration and so on). Consider the following popular
rhythmic beat, which is autosimilar with ratio 3 and offset 1:
Definition 2.1 Let M be a periodic melody with period n. M is autosimilar with ratio a and offset b iff
symbolically a M + b = M , i.e.
∀k ∈ Zn Ma k+b = Mk
Theorem 2.2 Any autosimilar melody of ratio a, period n, and offset b is built up from orbits of the affine
map x 7→ a × x + b mod n.
The proof is identical to that of Thm. 1.21 .
Remark 1 This new, more general setting, includes the case a = 1 with melodies invariant under x 7→ x+τ ,
i.e. maps with a period smaller than n. Each orbit, and hence each preimage
M −1 (p) = {k, Mk = p}
1 The mathematical view would be here to define an action of Aff on the set of maps M : Z → (pcs) by f [M ] = M ◦ f . We will
n n
make use loosely of this formalism in writing a M + b for the sequence k 7→ Ma k+b .
GGGE[ 9
is then a Limited Transposition Subset of Zn . We will henceforth drop this case and assume a1.
Remark 2 The setting of affine maps modulo n might be unfamiliar to many readers, and a few reminders
may be useful. The main point is to distinguish between the monoid of general affine maps, and the group
of affine transformations, which are one-to-one maps; these last are exactly the x 7→ a x + b mod n with
gcd(a, n) = 1. Their group Aff n is a semi-direct product of its translation subgroup (all x 7→ x + b),
isomorphic to the group Zn , and its homotheties subgroup (all x 7→ a x, gcd(a, n) = 1) which is isomorphic
to Z∗n ; Aff n is not abelian and several open problems remain about its structure. [10] is quite right in
demanding that the exact sequence
(which is another way of expressing the semi-direct product structure of Aff n we mentioned) be taken into
account; but it is not sufficient to explain all that we will encounter.
For instance, the Kientsy Loops 1 melody G F E D E F G D G F E D E F G D. . . can be viewed as
generated by x 7→ 3x + 6 mod 8 if origin is G=0:
0 1 2 3 4 5 6 7 ...
6 1 4 7 2 5 0 3 ...
G F E D E F G D ...
True, it can be viewed more simply as generated by x 7→ 3 x if we decide that the consecutive F, E stand
on positions 0,1. This ambivalence will be elucidated in a little while.
If this is equal to x, for all x, then by substracting between x and x + 1 one gets condition ak − 1 = 0;
and putting in x = 0 yields b × (1 + a + . . . ar−1 ) = 0. As ak − 1 = (a − 1) × (1 + a + . . . ar−1 ) and (by
Bezout’s identity) there exists some u, v with ub + v(a − 1) = gcd(a − 1, b), this means that the condition
of the lemma is satisified.
Conversely, if it is satisified, as gcd(a − 1, b) divides both a − 1 and b, then ak − 1 = 0 and b × (1 + a +
. . . ar−1 ) = 0 which yields exactly f k (x) = x ∀x ∈ Zn .
In practice, compute the ‘missing factor’ mf = n/ gcd(a − 1, b, n), and look up the first number 1 + a +
. . . ar−1 that is a multiple of mf .
Proposition 2.4 o(f ) is a multiple of o(a), and a divisor of the smallest integer s satisfying
1 + a + a2 + . . . as−1 = 0
We leave the proof as an exercise (consider the periods of sequences f k , ak , and 1 + a + a2 + . . . ak−1 , or
alternatively the sequence 1).
All these numbers are identical for instance when a − 1 is coprime with n, as then
(x7→a x+b)→a
0 −→ k Zn ≈ Zτ ≈ gr(x 7→ x + k) −→ gr(f ) −→ gr(a) ⊂ Z∗n −→ 1
On the other hand, with g : x 7→ 3 x + 2 mod 8, though g 2 = id, strangely g admits no fixed point.
As in section I, we get
Proposition 2.7 The length of any orbit is a divisor of o(f ).
The metaphor of clocks (see fig. 6) is the same as in the case b = 0: all smaller clocks must have looped
to initial position when a ‘day’ is spent, that is to say when f has been iterated a number of times that
equals it to identity1 .
This means that the number of occurences of a given note divides o(f ) – but this stands only if
the melody is primitive: random reunions of orbits would put of course this result into shambles.
Surprisingly, one result from the easy case b = 0 (and even n prime) is still valid:
1 This is a special case of a general result in group action theory: cardinals of orbits of a finite group divide the cardinality of the
group, and more precisely the quotient is the cardinality of the subgroup fixing some given element of the orbit. Here this subgroup is
gr(f ).
2 o(f ) = n for instance when f (x) = x + b, b ∈ Z∗ . These maps are conjugates in Aff of the basic translation x 7→ x + 1. It happens
n n
also, surprisingly, for non translations, like x 7→ 5 x + 1 mod 8 or x 7→ 16 x + b mod 45, gcd(b, 45) = 1.
3 except for n = 2; here Φ denotes Euler’s totient function
4 A permutation with cycles (= orbits) of lengths 3, 4 and 5 has order 60.
GGGE[ 11
a map that permutes n objects is the lowest common multiple of the cardinalities of its orbits, which is
usually more than the greatest among these cardinalities.
a−1 b
Let α = (a − 1) ∧ b and u = , v = : u, v are coprime integers, hence choosing some large x0 prime
α α
in the sequence as above, which implies coprimality with n [if x0 is large enough it will not be a prime
factor of n] we have:
a−1 b
Lemma 2.9 There exists x0 with u x0 + v = x0 + invertible (modulo n).
α α
We then compute the length of Ox0 :
As seen in Lemma 2.3, this implies that o(f ) is a divisor of k, which completes the proof.
Example 2.11 : It is remarkable that the length of an orbit can appear unconnected with the order of a:
the addition of b in the map f : x 7→ a x + b changes the behaviour of f tremendously. For instance, though
72 = 1 mod 12, the orbits of x 7→ 7 x + 2 mod 12 have length 3 or 6 (this last being the order of f ).
On the other hand, not all divisors of o(f ) are lengths of orbits, just as not any divisor of the order of
a group corresponds to a subgroup. Still a composer might wish to repeat some note a given number of
times, and so try and find the appropriate map f ∈ Aff n . It may appear surprising, for instance, that there
exists orbits of length 5 in 22-periodic melodies. But this is a corollary to a well-known lemma attributed
to Cauchy: as the whole group Aff n is of order n × Φ(n),
Proposition 2.12 (from Cauchy’s Lemma)Let p be any prime factor of n or Φ(n), there is an element
of f ∈ Aff n with order o(f ) = p.
The interest is of course that unexpected, new prime factors crop up in Φ(n). This is particularly
interesting when using general affine transformations because one gets prime factors that do not occur in
n. More generally, any result on the order of elements of group Aff n , e.g. Sylow theorems and the like1 ,
can be interpreted as a result on lengths of orbits2 .
1 Composer Tom Johnson suggested that these textbook theorems on finite groups be applied to the context of autosimilar melodies
2 Forinstance, if n = 2v(2) pv(p) q v(q) . . . , it could be shown that there exists an element of Z∗n with order pv(p) q v(q) . . . times some
power of 2 (usually 2v(2)−2 ), or any divisor of this. This maximal value is called Λ(n), see note above on Carmichael’s function.
12 autosimilar melodies
With this new origin we have reduced f to the simpler case of section 1.
Geometrically this is obvious, if one is willing to convey his or hers intuition of affine maps into Zn : if
f fixes z ∈ Zn , then as f is affine it is completely determined by the value of f (z + 1) = f (z) + a. But
the homothety hz,a with center z and ratio a gives the same values in z, z + 1, so it IS f . There is also a
numerical test, that the reader may check with a direct computation:
Theorem 2.14 f is an homothety up to a change of origin if and only iff f (x) = a x + b with b a multiple
of a−1 in Zn (if b is to be read as a true integer in N, this reads as “ b must be a multiple of gcd(a−1, n)”).
It is worthy of note that
• If f is an homothety (i.e. admits some fixed point) then o(f ) = o(a), but
• the converse is not true: map x 7→ 3 x + 1 mod 10 has no fixed point at all but is of order 4, just the
same as its ratio: 34 = 81 = 1 mod 10 and 3(3 x + 1) + 1 = 9 x + 4 = 4 − x mod 10, 4 − (4 − x) = x.
Two orbits have length 4, and the other has length 2.
2.4.2 Number of fixed points. Contrarily to our intuition in planar geometry, an affine map mod n
may well have several fixed points, e.g. ’centers’.
Proposition 2.15 Let d = gcd(a − 1, n): if d | b (in N) then we get d fixed points. Else there is none.
a−1 b n
(a − 1)x0 = b mod n ⇐⇒ x0 = mod
d d d
a−1 n
and as and are coprime, we get one solution modulo n/d, that is to say d solutions modulo n.
d d
(for example : x 7→ 3x + 2k + 1, n = 2p has no fixed point).
So an homothety might have different centers, that is to say an autosimilar melody can be related to the
simplest case in more ways than one. Musically this allows to show the autosimilarity on different circular
permutations of the initial melody.
2.4.3 Number of homotheties. From theorem 2.14 above we can easily compute the number of homo-
theties in Aff n , as it is a simple matter to enumerate all acceptable b’s for a given a, which are all multiples
GGGE[ 13
of gcd(n, a − 1):
Proposition 2.16 The number of homotheties in Aff n , identity map excluded, is given by formula
X n
Nhom (n) =
gcd(n, a − 1)
2≤a≤n−1
gcd(a,n)=1
Its maximum value is achieved when n is prime, as for all values of a, gcd(n, a − 1) = 1 and hence
Nhom (n) = n(n − 2) = (n − 1)2 − 1, among n2 − n affine maps. By contrast, Nhom (30) = 63 only; and
almost one affine map out of 3 is a homothety when n is a power of 2. It seems that 4,6 and 12 are the
only values of n with Nhom (n) < n. The proportion of homotheties among general affine maps, depending
much on the factorisation of n, is pretty erratic:
1.0
0.8
0.6
0.4
10 20 30 40 50
On average and for practical purposes, the proportion of homotheties in Aff n is around 57% for 3 ≤ n ≤
200.
Theorem 2.17 The maximum number of different notes for an autosimilar melody with period n is 3n/4,
which is reached exactly when n = 4k, a = 2k + 1 and b is 0 or n/2.
In general, the total number of notes (or orbites) varies wildly with the modulo and ratio. There is a
formula, making use of stabilizer groups and the celebrated ’Lemma that is not Burnside’s ’ of group theory
and combinatorics, but it is more efficient computationally just to compute all orbits and enumerate them.
Here is this formula, wherein X(g) is the number of fixed points of g ∈ Aff n (computed from Prop. 2.15):
(
k k dk if dk | b(1 + a + . . . ak−1 )
Proposition 2.18 Let r = o(f ), dk = gcd(a − 1, n) and X(f ) = .
0 if not
The total number of notes, i.e. of orbits under the action of f , i.e. under action of the group G = gr(f ) ⊂
14 autosimilar melodies
Aff n , is
r
X 1X
X(f k )
Xg |G| =
r
g∈G k=1
Here is a plot with the mean value of the number of different notes for any given n, mean taken on all
ratios a > 1 coprime with n and all possible offsets b.
15
10
20 40 60 80
These computations enable to compute a fairly reasonable1 value of the probability for a melody to be
[primitive] autosimilar, namely the number of partitions of Zn into affine orbits, over the number of all
partitions (e.g. 2n ). This probability decreases quickly, for n = 20 it is p = 0.000084877 and for n = 72,
with only 480 partitions into affine orbits, the probability is negligible (≈ 10−19 ). Whatever the propriety of
this mode of calculation of a probability, it shows that autosimilar melodies are highly organised material,
and that autosimilarity is a significant feature indeed.
3 Other symmetries
We will remain in the more general context of affine automorphisms x 7→ a x + b, not only homotheties.
Definition 3.1 The symmetry group of a (periodic) melody M is the subgroup of Aff n containing all
maps g satisfying g[M ] = M , that is to say ∀k Mg(k) = Mk . One says that g stabilizes M .
Two extreme examples are a melody that is not autosimilar, meaning its symmetry group contains only
the identity map; and the melody with only one note, which has the whole group Aff n for symmetries.
The Alberti bass C G E G C G E G . . . admits all odd ratios for autosimilarity, and more precisely its
symmetry group is made of eight distinct maps mod 8 (check this is an abelian group):
1 There are many different ways to define a probability space on melodies, and about as many different probability values.
GGGE[ 15
As any autosimilar melody is built up from some map f ∈ Aff n , it is obvious that any f k stabilises the
melody. Indeed this means exactly that the melody IS autosimilar under map f . A partial reciprocal is
true:
Theorem 3.2 Let M be a primitive autosimilar melody generated by map f : x 7→ a x. Then any homothety
g ∈ Aff n , e.g. g(x) = c x that stabilises M , is a power of f , e.g. ∃k c = ak .
When c is no power of a, g permutes the orbits, that is to say stabilises the rhythmic structure of
the melody, while exchanging its notes.
Proof Assume g(x) = c x stabilises M . In particular, the orbit O1 which contains powers of a is globally
invariant under g, meaning g(1) = c ∈ O1 is some power of a, qed.
If c is not a power of a, as we have seen already, maps of the kind x 7→ c x turn Ox into Oc x .
This means, quite significantly, that in considering only the simpler affine maps (homotheties), only the
obvious symmetries will occur. The picture is of course different in the whole affine group, and we do not
have a general result. Of course, nothing can be said when the melody is not primitive as collapsing some
orbits together will increase the symmetry group. Apart from the Alberti Bass, we quote below (fig. 18)
one page of the score of Loops for Orchestra by Tom Johnson, composed by Tom Johnson, wherein the
melody admits several different ratios.
A redeeming feature is the fact that many (more than half) affine maps are indeed homotheties, up to
a change of origin. In this case the result is simple:
Theorem 3.3 If f : x 7→ a x + b is a homothety (from Thm 2.14, this means that gcd(a − 1, n) divides
b), then the symmetry group of any primitive autosimilar melody built from f is just the group of powers
of f .
Proof Let us assume, up to a change of origin, that 0 is a fixed point of f . Then (0) is an orbit, stable
under any element of the symmetry group. This means that all these maps are of the form x 7→ c x and
by the last theorem they must be powers of f .
Remark 1 One could also look for the larger subgroup of Aff n preserving the set structure of orbits –
meaning exchanges of notes are allowed. In the case of the theorem above we fall back on the whole group
of homotheties, isomorphic to Z∗n .
In the more general case, the situation can be pretty complicated: for instance the map x 7→ 3x + 1
mod 8 (cf. Fig. 8) builds up the melody CCGGCCGGCCGGCCGGCCGGCCGG. . . which admits as
many symmetries as the Alberti bass:
x 7→ x, x + 4, 3x + 1, 3x + 5, 5x, 5x + 4, 7x + 1, 7x + 5
Complicated symmetry groups are possible (this last one, sometimes called H8 , is not abelian). As all
powers of f are in the symmetry group, we can at least predict that
Lemma 3.4 The order of the group of symmetries of M is a multiple of o(f ).
Proof o(f ) is the order of a (cyclic) subgroup of the symmetry group, hence divides its order by La-
grange’s theorem.
It is interesting for composers, and maybe analysts alike, to find a melody with a given symmetry
group. This is a kind of ‘inverse Galois problem’. For instance one may wish to find an 8-periodic melody,
palindromic, and autosimilar with ratio 3. Hence the orbit of 1 must contain −1 = 7 (for palindromicity);
as it contains 3, 5 = 7 × 3 is there too. Hence O1 contains all odd numbers.
Acting similarly with the remaining residue classes, one finds the primitive solution O1 = (1, 3, 5, 7), O2 =
(2, 6) with 4 and 8 standing alone as fixed points. One rendering of this unique solution is none other than
16 autosimilar melodies
the Alberti Bass. This leads to the most general definition so far, which indeed should be the starting
point for the study of melodies invariant under some affine maps1 :
Definition 3.5 An autosimilar melody M with period n and symmetry group G ⊂ Aff n is any map
M : Zn → (some pitch set) that satisfies
∀f ∈ G ∀k Mf (k) = Mk
Theorem 3.6 Such a melody is built up from the orbits of G, i.e. each pitch appears on indexes that are
a reunion of orbits Ox = {f (x), f ∈ G}.
Algorithmically speaking, one usually wishes to consider only some symmetries in G. An orbit will be
produced by repeatedly applying the given affine maps, starting with a given seed, until no new number is
produced1 . This last definition reduces to the above one when the group of symmetries is cyclic, generated
by just one map.
It must be pointed out that the group of symmetries eventually achieved is usually larger than the group
one starts from; not any odd group is the symmetry group of some object: for instance modulo 8, this
Klein group
K = {x 7→ x, x 7→ 3x + 1, x 7→ x + 4, x 7→ 3x + 5}
(0, 1, 4, 5) (2, 3, 6, 7)
and the symmetry group of any melody built up from these [say C C G G C C G G. . . ] is strictly larger
(for instance it contains x 7→ 5x + 4), with 8 elements.
Remark 2 Musically speaking, for such an autosimilar melody with a non cyclic group of affine symmetries,
it is possible to extract the melody from itself at different ratios, as can be seen on fig. 11 made in
OpenMusic. A similar situation will arise in the last section.
3.2 Palindroms
Now we can clarify when a given autosimilar melody will be a palindrom, as this means exactly that
x 7→ −x is an element of the group G of symmetries. Here is an example, in figure 12. At least this is
crystal clear when G is generated by ha : x 7→ a x, as we have seen that the symmetries must be powers
of ha :
Theorem 3.7 M , primitive autosimilar melody with ratio a, period n and offset 0, will be palindromic
⇐⇒ some power of a is equal to −1 mod n.
The question of whether -1 is a square modulo n (a quadratic residue) is pretty well known, but the
concept of -1 being a power residue appears to be novel. The sequence of moduli n admitting such a
possibility: 5, 7, 9, 10, 11, 13, 14, 17, 18, 19, 21, 22, 23, 25, 26, 27, 28, 29, 31, 33, 34, 35, 36, 37, 38,
39. . . has been added to Sloane’s online encyclopedy of integer sequences under number A1269492 . It is a
rather common occurence.
1 The implementation of the construction of such a melody has been made available to composers and other musicians in the software
OpenMusic, [2].
1 The underlying idea is that: any orbit is a fixed point of the action of any set of generators of G on the set of all subsets of Z . This
n
was implemented in OpenMusic, cf. [2].
2 http://www.research.att.com/ njas/sequences/A126949
GGGE[ 17
For instance mod 25, 2, 3, 4, 7, 8, 9, 12, 13, 14, 17, 18, 19, 22, 23 all have some power equal to −1; on the
other hand, there are no such powers modulo 6, 8, 12, 15, 16, 20, 24, 30, 32. . .
Again, this stands only for primitive melodies. Of course, it is always possible to build a palindromic
(autosimilar) melody from any autosimilar melody by just collapsing together notes belonging to orbits
that are symmetrical (the map x 7→ −x exchanges orbits of a primitive autosimilar melody with ratio a
and offset 0). For example see the original and the palindromized on figure13.
What of a melody autosimilar with offset ? For it to be an exact palindrom, the condition above is
still necessary, but not always sufficient as seen from this example: the map x 7→ 3x + 1 mod 8 generates
orbits (0, 1, 4, 5), (2, 7, 6, 3) and melody A A B B A A B B . . . which is not, strictly speaking, a palindrom,
though it becomes one by allowing an offset of the origin. This is general:
Theorem 3.8 Let M , primitive autosimilar melody generated by f : x 7→ ax + b mod n; if some power
18 autosimilar melodies
Proof Assume that ak = −1. Then f k (x) = −x + c for some c and hence M = f k [M ] = −M + c, i.e. M
is palindromic with a different starting point.
The reciprocal, unfortunately, is false when the map is not an homothety. For instance, no power of 3
equals -1 modulo 8, though x 7→ 3x + 1 generates a palindromic melody with offset. Still for some pairs
(a, n), there are no b’s at all that will allow x 7→ a x + b to generate a palindrom, e.g. x 7→ 8x + b mod 15.
3.3.1 A conjecture. The last paragraphs enable to clarify a conjecture from Johnson, which quite
uncharacteristically happened to be wrong (and was proved so in [5]). This was the conjecture ( [7]):
A related melody produced by playing a melodic loop [= a periodic melody] at some ratio other than 1:1, can
never be the inversion of the original loop, unless it is also a retrograde of the original loop.
What Tom means by ‘related melody’ is just some f [M ] = (Mf (k) )k∈Zn ; an autosimilar melody is precisely
a melody M that is equal to one of its related melodies.
Here we are looking for periodic melodies satisfying a condition
For this to happen, we need the musical space wherein M takes its values to possess some minimal algebraic
structure, which is usually true in most models.
The conjecture states that the above condition implies
Feldman, who first in history shed a mathematical look on these melodies (he used some himself as a
composer) but unfortunately only ever published the short [5] about them, shrewdly points out that Tom’s
conjecture will be true when n is prime [and f is homothetic] and provides a counterexample with period
15.
The inversion condition implies that M itself is autosimilar under f 2 , as
∀k Mf 2 (k) = p − Mf (k) = p − p − Mk = Mk
As the inversion acts on the orbits of f , they must have even cardinality: let us consider the simpler case
f (x) = a x, say 1 is pitch x, then a is pitch p − x, a2 is pitch x again, a.s.o. What we want to avoid in
order to disprove the conjecture is −1 ∈ O1 , as then the melody would be invariant under x 7→ −a x. As
seen above, -1 is often a power residue (this explains Johnson’s error) and, for instance when n is prime,
if a is of even order 2k then −1 = ak as ak 6= 1 is the only other solution of X 2 = 1 in the field Zn (this is
Feldman’s argument). But in Z15 for instance, X 2 = 1 has other solutions (eg 4); taking a = 2, n = 15 and
filling in the ordered orbits (1 2 4 8), (3 6 12 9), (5 10), (7 14 13 11) with alternate opposite values of one
note (0 is C, 1 is C], 2 is B, a.s.o.), we get by construction Mf (k) = −Mk ∀k, close to Feldman’s example.
3.3.2 The ratio that retrogrades. This suggests to look also for melodies with one alternate melody
being its retrograde. While composing we found (C D E C D F C D G C D E . . . ), autosimilar with period
9, ratio 4 and offset 6: picking every odd note turns the melody into its retrograde (up to offsetting): (C
E D C G D C F D C E D C . . . ), i.e. 2M + 1 = −M + 8. As it happens, this is a general phenomenon,
and it has nothing to do with 4 being a power of 2, quite the reverse:
GGGE[ 19
Figure 14. One note out of two gives inversion, not retrograde
Proposition 3.9 Let M be an autosimilar melody with ratio a and any offset; put c = −a−1 mod n;
then picking one note every c yields the retrograde −M (up to some offset).
n−1
This is most easily audible when c = 2, i.e. when a = (for some odd n!)
2
Proof Symbolically M = a M + b, hence c M = c (a M + b) = −M + c b, meaning ∀k Mck = Mc b−k .
In musical terms, this means that among the augmentations of any autosimilar melody, the retrograda-
tion of the initial melody can always be found.
3.3.3 Inverse-retrograde symmetry. The last situation is about melodies whose inverse IS the retro-
grade (like in Johnson’s conjecture).
For instance, with f : x 7→ 3x + 1 mod 26 [no fixed points]:
It can be seen, and even better, heard, that O0 and O8 (resp. O2 and O3 ) are retrogrades one of
another. This allows a pretty rendition of the melody, setting opposite notes for symmetric orbits: then
the retrograde of the melody will be its inversion, as seen on figure 15 (the symmetry axis for pitches is
around F). It is a little difficult, in fact, to find an example of an autosimilar (primitive) structure without
such a symmetry (this is related to Tom’s conjecture). For one thing, if f is an homothety (recall this
happens whenever a − 1 | b in Zn , for instance when b = 0), then x 7→ −x permutes the orbits, as all other
homotheties do. Also if some power of a is equal to c − 1, we get directly a palindrom.
Still an autosimilar melody built from 4x + 1 mod 21 does the trick, as its orbits (0, 1, 5), (2, 9, 16), (3,
11, 13), (4, 6, 17), (7, 8, 12), (10, 18, 20), (14, 15, 19) exhibit no inversional symmetry whatsoever. There
is a condition ensuring that such retrogradation symmetries between orbits exist:
Theorem 3.10 Assume a − 1 divides 2b, 2b = c(a − 1), then all orbits are permuted by the symmetry
x 7→ −c − x, i.e.
∀x ∈ Z/nZ O−x−c = −c − Ox
It can then easily be checked that g = Ic : x 7→ c − x will commute with f : x 7→ a x + b on the condition
that 2b = c(a − 1) mod n.
These examples open a new alley for future research, combining inner symmetries (the autosimilarity)
of a melody with outer symmetries (e.g. inversion), using some structural features of the space of musical
events.
This is about some mosaics, or tilings, which are deduced from some autosimilar melodies.
Proof Consider the orbits of 0 and 1: O0 = (0, b), O1 = (1, a + b). If we have a tiling then O0 + τ = O1 for
some τ . This τ cannot be 1 lest a = 1; hence τ = 1−b = a+b. We get a = 1−2b. Now notice O2 = (2, 2a+b).
If it is a translate of O0 then it is either by 2 or by 2 − b. In the latter case, 0 + (2 − b) = a + b which leads
to a contradiction. So it is 2a + b = b + 2, hence 2a = 2 which admits only the solution a = 1 + n/2 as
a = 1 is forbidden. Notice that n must be a multiple of 4. Moreover k must be odd or else f will not be
of order 2, as we see in the reverse:
Conversely, if n = 4k, a = 2k + 1, b = ±k then
so o(f ) = 2, with f (x) − x = 2kx ± k being allowed only two (opposite) values.
Going from one orbit to the next is like braiding a girdle, as each is reversed from the other while
translated.
Remark 1 It is easier to build tiles with unions of orbits of an affine map but we have no general result.
Indeed the question of tiling/autosimilar arose when Tom Johnson found (0, 1, 3, 7, 9) which tiles Z20 by
translation and also with ratio 3.
Remark 2 It is still an open question whether it is possible to find non periodic tiles of length > 2 (Vuza
Canons) in this fashion. A necessary condition is the absence of translations in the symmetry group, and
notably o(f ) = o(a).
In the simplest case n prime, b = 0, we get tilings of Z∗n with augmentations as any orbit is an augmentation
of O1 . In a manner of speaking, this works for any autosimilar melody, but with overlapping, so it is not a
bona fide tiling: for instance with f : x 7→ 3 x mod 8 the augmentations of (1 3) are (0 0), (2 6), (4 12=4)
and (5 15=7), O4 overlaps with itself when played as (4 12).
There is a better way to obtain a whole family of tilings with particular affine maps. But the tiles will
no longer be the orbits: on the contrary they will be sets transverse to them.
Lemma 4.3 Any autosimilar melody whose orbits share the same length enables to build tilings with
augmentation.
Proof Consider any set transverse with the orbits, i.e. X containing one point and only one from each
orbit. Then X, f (X), . . . f r−1 (X) partition Zn i.e. X tiles with augmentations a X + b a.s.o.
Example 4.4 All the orbits of f : x 7→ 13 x + 3 mod 20 have length 4: (0 2 3 9), (1 6 11 16), (4 15
17 18), (5 7 8 14) and (10 12 13 19). Take for instance the first elements: X =(0 1 4 5 10). Applying f
yields all following members of each orbit: f (X) = (3 16 15 8 13). Iteration of the process gives a mosaic,
where all motives are images of the preceding one by the map f . Notice that one can choose any starting
element in each orbit.
Now we would like to know when this can happen. We have no simple arithmetic characterization, but a
few interesting conditions. Notice that a − 1 is not allowed to divide b (in Zn ), which excludes a − 1 being
coprime with n in Z, or b = 0, or else we have fixed points.
Lemma 4.5 All orbits have the same length whenever the smallest orbit has length (some multiple of )
o(a).
Proof Let x0 have the smallest orbit: ((a − 1)x0 + b)(1 + a + . . . am−1 ) = 0 and
As x(a − 1)(1 + a + . . . am−1 ) = 0 for m is a multiple of o(a) and ((a − 1)x0 + b)(1 + a + . . . am−1 ) = 0 by
assumption, this works.
Other implication: if all orbits share the same length, we know it is the order of f , which is a multiple
of o(a).
It boils down to a cross product between the factors of arithmetic sequences with ratio a − 1 and of
partial sums of the geometric sequence with ratio a:
Theorem 4.6 All orbits will have the same length ⇐⇒ ∀x
((a − 1)x + b) × (1 + a + . . . am−1 ) = 0 ⇒ am = 1 (5)
that is to say one cannot have ((a − 1)x + b) × (1 + a + . . . am−1 ) = 0 without o(a) dividing m.
Proof Assume all orbits have the same length, i.e. that length is a multiple of o(a). The length of Ox is
the smallest r such that
By assumption this is a multiple of o(a). Hence ar = 1. Notice this implies that b × (1 + a + . . . ar−1 ) = 0
too.
22 autosimilar melodies
this means f m (x) = x and m is a period of f on Ox . As seen previously this means that m is a multiple
of r, length of Ox : again am = 1.
In the other direction: assume that ((a − 1)x + b) × (1 + a + . . . am−1 ) = 0 implies that am = 1, i.e.
o(a) | m. This means exactly that all orbit lengths are multiples of o(a), by the lemma above, it proves
that all orbits are the same length.
Example 4.7 For instance, for 13 x + 3 mod 20, the sequence of the 1 + a + . . . am−1 takes values 1, 14,
3, 0 cyclically. The order of a = 13 is 4 mod 20. If b = 3, one computes b + x(a − 1) = 3, 15, 7, 19, 11,
neither of which gives 0 when multiplied by 1, 14 or 3. So the condition is verified, as it is for b = 7, 11, 15
or 19 or indeed any odd b.
But for (say) b = 2, it does not work (|O4 | = 2). The sequence (12 x + 2)x=0...4 contains 10 (for x = 4),
and this enables ((a − 1)x + b) × (1 + a + . . . am−1 ) = 0 for m = 2 < 4, i.e. an orbit of length 2 instead of
4.
There is little hope of simplifying this condition: one has to look into the sequence 1 + a + . . . am−1 (m
varies from 1 to some divisor of o(f )) for factors c common with n, and look for arithmetic sequences
(b + x(a − 1)) (x from 0 to n/ gcd(n, a − 1)) that do NOT provide the missing factors n/c. In the last
example, the only possible case was with m = 2, 1 + a = 14, common factor 2: one had to find arithmetic
sequences with ratio 12 with no term a multiple of 20/2 = 10.
Remark 3 When equal length orbits are longer than o(a), it means that o(f ) > o(a). In that case, all orbits
will be periodic, as they will be invariant under f o(a) which is a translation (not identity by assumption).
For instance with
But such inner symmetries cannot happen when o(a) = o(f ), as we have seen with x 7→ 13 x + 3 mod 20.
Remark 4 Say a = n − 1 for some even n. f : x 7→ 2k + 1 − x mod n is a map with all orbits of length
2. Omitting those ‘trivial’ solutions, the first values of (n, a) giving such tilings are (with adequate values
for b)
(8, 3) (8, 5) (12, 5) (12, 7) (16, 2k + 1) (18, 7) (18, 13) (20, 9) (20, 11) (20, 13) . . .
Some other families of solutions could be devised likewise, e.g. when n = 4k, a = 2k±1, f : x 7→ (2k−1)x+1
has orbits of length four. But musically (following Tom Johnson’s advice) it is better to keep to small values
of a, so we won’t pursue this line.
5 Approximate autosimilarity
In a way, autosimilarity in a (periodic) melody is a special form of redundancy: as we have seen by now,
autosimilarity is an aural illusion, where identical notes are identified though lying in fact in different
positions in the original melody and in its augmentation. It is a legitimate question to ask for approximate
autosimilarity: what if some melody is autosimilar apart for a few notes ? With which ratio ? It turns
out this can be investigated with a simple algorithm, and also that such relaxed autosimilarity appears
surprisingly often in the corpus of classical music.
GGGE[ 23
5.1 Algorithm
Let M be some melody with period n. We define the periodic augmentations of M as the a × M + b in
symbolic notation, meaning the sequences (Ma k+b mod n )k∈N . As seen above, M is autosimilar iff a × M +
b = M for some a, b. We can compute a correlation coefficient between all a × M + b and M itself by
checking the proportion of notes that are the same – technically it is a comparison of circular lists, or
circlists, between M and a M . Checking for maximum on b, then a, allows to find the best candidate for
autosimilarity. Here is an implementation in MathematicaT M , with the trick for comparison that Union is
applied to pairs Mk , Ma k+b in order to count for singletons i.e. the number of coincidences:
correl[melo_, a_]:= Module[{n=Length[melo], meloBis},
(* local variables *)
meloBis = Table[melo[[Mod[a*(k+decalage)-1 , n]+1]], {k,n},{decalage, n}];
(* this is the alternate melody a*M+ decalage *)
Max[(Count[Length/@ (Union /@ Transpose[{melo, #}]), 1])& /@ meloBis]/n]
5.2 Example
It is fairly obvious that no autosimilarity will be found when all notes are different – the melody cannot
be broken down into orbits in that case. But with repeated rythmic motives involving repeated notes,
autosimilarity may well be found. The first melodic sentence of Beethoven’s fifth exhibits very good
autosimilarity when cut down to 12 notes: G, G, G, E[, A[, A[, A[, G, E[, E[, E[, C has a correlation
coefficient of 5/6 for x 7→ 7 x + 6. Musically this means only two notes are not identical in the augmented
version. These alien notes have been written down as a chord together with the ‘expected’ note on the
score (notice though the octave identification for E[’s).
This algorithm should hopefully be run with good results on a lager corpus of classical or Jazz music,
as it did strike gold on the first try. It is also part of the routines looking for ‘interesting melodies’ in the
OMax software for improvisation.
6.1 Definition
The condition that the ratio a be invertible modulo n may appear as a little artificial, a convenience in
order to allow the mathematical tools to come in. Actually the initial definition can work well with any
ratio (not zero), as for instance melody
D, G, F, G, D, G, F, G, D, G, F, G, D, G, F, G, D, G, F, G, D, G, F, G . . .
with period 24 is certainly autosimilar with ratio 3, though 3 is not coprime with 24. Of course it will be
argued that here, the smallest period (4) IS coprime with 3. So we have to consider what happens when
iterating an affine map that is not bijective.
Example 6.2 Consider this seemingly random sequence of 36 notes as a periodic melody:
D, C, G, G, B, F, A, B, F, H, B, E, B, B, G, H, H, C, E, C, C, E, E, E, H, H, E, A, C, E, E, E, D, F, H, E, (D, C, G . . . )
The two first iterations of map x 7→ 3x − 1 mod 36, that is to say picking one note out of three starting
with the second, yield
C, B, B, B, B, H, C, E, H, C, E, H, C, B, B, B, B, H, C, E, H, C, E, H, C, B, B, B, B,
B, B, E, E, B, B, E, E, B, B, E, E, B, B, E, E, B, B, E, E, B, B, E, E, B, B, E, E, . . .
the last of which is periodic and autosimilar: further iterations of the same transform will yield the same
melody. We notice that several notes have disappeared, and that the ultimate period is smaller than 36.
Proof The set (algebraically, a monoid) of all affine maps modulo n is finite. Powers of f thus will only take
a limited number of different values. So there must exist two different exponents p, p + q with f p = f p+q .
Now for any r > p,
We have shown a classical result: the sequence of powers of f is ultimately periodic. So is for any x ∈ Zn ,
the sequence f k (x). This means that after p iterations of f , any further iteration of f q will preserve the
sequence.
Now the algorithm that enables to construct such an ultimately autosimilar melody is straightfor-
ward:
GGGE[ 25
Definition 6.3 We generalise the definition of orbits to the attractor of x: Ax = {f k (x) | k ≥ p). It is
the part of the sequence f k (x) that loops (beware ! usually x ∈
/ Ax . . . ).
Now it only remains to ensure that, as in the preceding theorems about building up autosimilar melodies,
all notes with indexes in the same Ax are identical. In the above example, we have two attractors, A =
(5, 14) and B = (23, 32). The initially completely random melody M was modified is setting M14 = M5 =
B, M23 = M32 = E. All other notes are irrelevant. Musical applications could involve extracting a simple,
autosimilar beat, from a complex melody. Another nice application is to arrange the initial melody in order
to support several extractions of ultimately autosimilar melodies. For instance,
E, H, B, G, C, G, H, G, E, A, H, H, C, C, B, G, F, G, C, G, H, G, G, H, A, F, G, G, E, H, H, G, F, G, F, B . . .
gives two autosimilar melodies when augmented by 2 or by 3 by applying the same trick as above both
to the attractors of x 7→ 3 x + 1 and those of x 7→ 2 x. It is plainly visible on the ‘score’ below that two
(simple) autosimilar melodies emerge (the initial melody is the middle voice).
1 It is worth noticing that orbits, for homotheties, or their difference sets, for general affine maps, are exactly the eigenvectors of
Vieru’s difference operator acting on subsets of Zn : ∆(x, a x, a2 x . . . ) = (a − 1)(x, a x, a2 x . . . ).
26 autosimilar melodies
a = pm mk
1 . . . pk (k ≥ r)
1
n = pn1 1 . . . pnk k × Q = P × Q, with gcd(P, Q) = 1
then the sequence (ak x)k∈N is ultimately periodic, from at least the rank r verifying (n/q) | ar , i.e. the
smallest integer exceeding all ratios ni /mi .
n
The periodic parts of this sequence, i.e. the attractors Ax = {ak x, k > r}, partition the sub-group Zn
q
of Zn , isomorphic with Zq .
Proof We use the Chinese Remainder Theorem: the ring Zn is isomorphic with the ring product ZP × ZQ
(meaning essentially that any residue class modulo n is well and truly determined by its residues modulo P
and modulo Q). Thus any (affine) map in Zn can be decomposed into two (affine) components on ZP and
ZQ : if x ∈ Zn corresponds to (y, z) ∈ ZP × ZQ then f (x) corresponds with (fb(y), fe(z)) where fb(y) = f (x)
mod P, fe(z) = f (x) mod Q.
Now for map f : x 7→ a x ∈ Zn : as ar = 0 mod P we have fbr = 0 (the null map), i.e. fb is nilpotent;
conversely, as a is coprime with Q, the other component fe is one to one. After k ≥ r iterations, f k reduces
to (fbk , fek ) = (0, fek ) and we are back to section 1.
Remark 1 The result of r iterations of f on the original melody is not necessarily invariant under f itself,
but as proved above, it is always invariant under f τ where τ is the order of fe. In other words, it has at
most τ ‘alternate melodies’ (under iteration of f ). Though in theory one might stumble on the case f τ = id
(for instance if the original melody has n distinct notes), in practice one frequently does find some non
trivial attractor. In this sense, autosimilar melodies are exactly the attractors of any affine map operating
on any initial (periodic) melody, thus reaching the elated status of universal object.
Acknowledgements
First and foremost I must thank and congratulate composer Jom Johnson for his pioneering work on the
subject and the wonderful music he managed to make out of this basically simple idea. Also I am grateful
to Gerard Assayag who introduced me to the notion over a glass, and later put the question of detecting
approximate autosimilarity. Carlos Agon implemented it in OpenMusic T M and is therefore responsible
for several nice illustrations in this paper, while Moreno Andreatta helped clarify a number of less than
obvious points.
References
[1] Amiot, E., Why Rhythmic Canons are Interesting, in: E. Lluis-Puebla, G. Mazzola et T. Noll (eds.), Perspectives of Mathematical
and Computer-Aided Music Theory, EpOs, 190–209, Universität Osnabrück, 2004.
[2] Amiot, E., Agon, C., Andreatta, M., Implementation of autosimilar melodies in OpenMusic.
[3] Andreatta, M., Méthodes algébriques en musique et musicologie du XXe sicle : aspects thé oriques, analytiques et compositionnels
, (2003) Ph.D. dissertation, EHESS.
[4] Andreatta, M., Agon, C., Vuza, D.T., Analyse et implmentation de certaines techniques compositionnelles chez Anatol Vieru, in
Actes des Journes dInformatique Musicale, Marseille, (2002), pp. 167-176
[5] Feldman, D., Self-Similar melodies, in Leonardo Music Journal, (1998) 8:80-84.
[6] Fripertinger, H., Tiling Problems in Music Theory in in: E. Lluis-Puebla, G. Mazzola et T. Noll (eds.), Perspectives of Mathematical
and Computer-Aided Music Theory, EpOs, 153–168, Universität Osnabrück, 2004.
[7] Johnson, T., Self-Similar melodies, (1996), Two-Eighteen Press, NY.
[8] Rahn, J., Basic Atonal Theory, (1980), Longman, New York.
[9] Morris, R., Composition With Pitch Classes: A Theory of Compositional Design, (1987), New Haven, Yale University Press.
[10] Mazzola, G., et alli, Topos of Music (2004), Birkhaüser.
GGGE[ 27
œœœœœœ
œ œ. œ. œ œ œ. œ.
52
Fl. 1 &b ! ‰ Œ Ó Œ Ó Ó ! ! Œ Ó Œ ‰ ‰ Œ ‰
œ œ. œ. œ œ œ. œ. œœ œ
Fl. 2 &b ! ‰ Œ Ó Œ Ó Ó ! ! Œ Ó Œ ‰ ‰ Œ ‰ œ œœ
œ œ. œ. œ œ œ. œ. œ œ
Ob. 1 &b ! ‰ Œ Ó Œ Ó Ó ! ! Œ Ó Œ ‰ ‰ Œ ‰ œœ œœ
œ. œ. œ. œ.
Ob. 2 & b !œ‰ Œ Ó Œ Ó Ó !œ!œŒ Ó Œ ‰ ‰ Œ ‰
œœœœœœ
# ! ‰ Œ
œ Ó Œ œ. œ. Ó Ó !œ!œŒ Ó Œ ‰ œ. œ. ‰ Œ ‰ œœœœœœ
Cl. &
# Ó Œ Ó Ó Œ Ó Œ
&
œ. œ œ. œ. œ. œ. œ. œ. œ. œ. œ. œ. œ. œ. œ. œ. œ. œ.
B. Cl.
Bsn. 1
?
b " " " " Ó ‰ œœœœœœ
?b Ó Œ Ó Ó Œ Ó ‰ œ
Bsn. 2
œ. œ œ. œ. œ. œ. œ. œ. œ. œ. œ. œ. . œ. œ. œ. œ. œ. œ.
.
Trb. 1
?
b " " œœœœœœ‰ Ó Œ !œœœœœœ!Œ Ó ‰ œœœœœœ
?b ‰ ‰ œ ‰ ‰ œ ‰ œ ‰ Ó " Ó ‰ ‰ œ ‰ ‰ ‰ œj
Tb.
œ. œ. . œ. . . œ. œ. . œ. œ. .
52
Vla.
B b œœœ!œœœœœœ‰ Œ Œ œœœœ!œœœœœœ! Œ ‰ !œœœœœœ!œœ œœœœŒ Œ œœœœ œ œ!œœœœœœ ! œ œ œ œ œ œ
? b œ. œ. œ. œ. œ. ‰ œ. œ. œ. œ. œ. œ. ‰ œ. œ. œ. œ. œ. œ. ‰ œ. œ. œ. œ. œ. œ. ‰ œ. œ. œ. œ. œ. œ. ‰ œ. œ. œ. œ œ œ œ œ œ
Vcl.
t b œ. ‰ œ. ‰ œ. ‰ œ. ‰ œ. ‰ œ. ‰ Œ .
œ. ‰ œ. ‰ œ. ‰ œ. ‰ œ ‰ œ. ‰ Œ
. . .
œ. ‰ œ ‰ œ ‰ œ. ‰ œ. ‰ œ ‰
Cb.