Of some rhythmic canons
À propos de certains canons rythmiques.

Acknowledgements.

I must bless, and curse, too, MMs. Andreatta, Fripertinger & Tangian whose works provoked me into this. I am indebted to them for many ideas that just seem to sprout randomly in what follows hereafter.
Tous mes remerciements et une amicale malédiction, vont à M. Andreatta, Fripertinger & Tangian qui m'ont convaincu par l'excellence de leurs travaux, de l'intérêt de la question des canons rythmiques.

Representation as product of 0-1 polynomials
Interprétation comme produit de polynômes 0-1
Graphical rendering / Représentation graphique

Surging from M. Tangian's paper, I will study rhytmic canons as products of 0-1 polynomials.
Je suis parti de l'idée de M. Tangian qui consiste à représenter des canons rythmiques comme produits de polynômes.

Clear[faitPosition, canonPlot, ca1, ca2];

faitPosition[a_, b_] := {a+b,b}

canonPlot[{p1_, p2_}, taille_:0.01]:= 
  Module[
    {l1 = CoefficientList[p1,X],
     l2 = CoefficientList[p2,X]},
     (* cherchons les coefficients égaux à 1 *)
     l1 = Position[l1, 1];
     l2 = Position[l2, 1];
    ListPlot[
        Partition[
            Flatten[
                Outer[faitPosition, l1, l2]
                    ],
                 2],
            PlotStyle->PointSize[taille],
            Ticks->{Automatic, {}} ,
            PlotRange->All
            ]
                            ]

ca1 = canonPlot[{1+X+X^4+X^5,
                 1+X^2+X^8+X^10+X^16+X^18},0.02];
ca2 = canonPlot[{1+X^2+X^8+X^10+X^16+X^18,
                 1+X+X^4+X^5}, 0.025];

Show[GraphicsArray[{ca1, ca2}], 
  PlotLabel -> StyleForm[
  "Deux canons économiques duaux", 
                  FontSize->16, 
                  FontFamily->"Palatino" ]];

A weak ring / Un anneau mou

I am firmly convinced there may be considerable interest to create ad hoc structures in between the "hard" mathematical ready-made structures (groups, Topoï…) and the "evasive" musical material. Instances are the rare unitary monoïd of interval classes (mod ), pinpointed by M. Andreatta, and the stranger group of matrixes with and  b,c  ∈  —‡/n—‡ which I would have smashed into small pieces (Jordan-Hölder like) for your benefit, had I not been diverted towards the rhythmic canons.
Hence the definition of the set ℵ of 0-1 polynomials. Several properties are at least partially preserved from its ancestors, (—‡[X],+,x) and the set of (finite) subsets of —±, which are abelian rings and more: for instance the composition laws +, x, / and °. Any element of ℵ has a (unique) decomposition in irreducible factors, there is distributivity, associativity, aso...
I had to coin a name, and will call ℵ a WEAK RING. But there is a price to pay:

Only partial stability:
Stabilité partielle seulement pour les opérations internes

p=Function[X, X^4+X^2+1];
q=Function[X, X^2+X+1];
Expand[p[q[X]]]
Clear[p,q];

The notion of ideal may be preserved — with care. But any ideal will still be principal (monogenous). For instance, the sum of two ideals shall be defined as
; Example:

This is important as ideals are a good way to study divisibility.

Which canons I am looking for / les canons qui m'intéressent

I wish to factor the polynomial as a product of two 0-1 polynomials, that is to say to tile the range [0, 1, 2, …, n-1] with one sub-pattern "without overlapping or gaps".
Je veux factoriser  dans ℵ, l' anneau mou des polynômes 0-1, c'est à dire paver l'intervalle d'entiers [0, 1,…, n-1] de façon bijective.

This is not a tiling of ! but

Any such factorization induces a periodic canon: say in terms of sets ; then .

The pitch-classes return with a vengeance, as such factorizations provide Limited Tranposition Modes (like Messiaen's, only tighter).

By analogy, one shall find factorizations in two terms of an integer by splitting its decomposition as a product of primes: for instance and hence .
Faisons un parallèle: on obtiendra les factorisations en deux termes d'un entier à l'aide de sa décomposition en produit de facteurs premiers: par ex d'où .

Such unique factorization in polynomials with integer coefficients is well-known for , by way of the cyclotomic polynomials .
Une factorisation en polynômes à coefficients entiers (unique à l'ordre près) est connue pour , ses facteurs iréductibles sont les polynômes cyclotomiques .

Table[{n,Cyclotomic[n, X]}, {n,100}]//TableForm//TraditionalForm

I just had to explore the possibility of factoring in 0-1 poly with the help of 's, because
• so many of them just are 0-1 polynomials and
• most of them are 0 - ±1 polynomials, which is not far from what we are looking for.
Je n'ai pas pu résister à l'idée d'explorer les factorisations 0-1  à l'aide des , car ces derniers
• sont souvent des polynômes 0-1,
• à défaut, sont presque toujours des polynômes 0 - ±1 ce qui n'est pas loin.

Some formulas about the / Formulaire sur les .

Basic properties

For prime, .

is the unitary polynomial with roots the primitive th roots of unity. Hence its degree is the Totient function applied to .
NB: yet another reason I jumped on these polynomials (consider the extensive use of the structure of invertibles in by Vuza or Fripertinger — and others !)

X/.Solve[X^2-X+1==0,X]//ComplexExpand

is the product of the where is any divisor of (1 excluded). These are the irreducible factors (in ).

Cyclotomic[6,X] Cyclotomic[3,X] Cyclotomic[2,X]//Expand

By Möbius inversion, is the product of the where μ is the Möbius function.

Cyclotomics, 0-1 polynomials, canons, periodicity.

For and primes and , is a polynomial in .
My first proof involved some Galois theory, strikingly close to one of the arguments of Vuza [V., 4] in the demonstration of his thm 2.1. But it is easier with the explicit formula involving the μ - function.
A generalization is known: for .

If is prime and does not divide , then (hence a 0-1 polynomial iff )

canonPlot[{1+X^4+X^8+X^12,1+X^3+X^6+X^9+X^12}];

For primes, IS a 0-1 polynomial.
Proof: (this gives a feeling of these things)
From the development (arising from a previous Lemma) it suffices to prove that the exponents are all different from one another. If it were not the case, then for some and one finds . Hence divides   and divides : but this is too rich, as (say) and . —R

Interesting canons

Trivial canons / canons triviaux

Some of these factorisations of are completely trivial and repetitive. This is the case when one of the factors is a for prime (or a power of a prime): the voice (pattern), AND the pattern of entries are metronomic (indeed such a factorisation MUST be !). Example for :

Map[canonPlot[#,0.04]&, 
{{X + 1, X^10 + X^8 + X^6 + X^4 + 
    X^2 + 1}, {X^2 + 1, 
   X^9 + X^8 + X^5 + X^4 + X + 1}, 
  {X^2 + X + 1, X^9 + X^6 + X^3 + 
    1}, {X^3 + 1, X^8 + X^7 + X^6 + 
    X^2 + X + 1}, {X^6 + 1, 
   X^5 + X^4 + X^3 + X^2 + X + 1}, 
  {X^4 + X^2 + 1, X^7 + X^6 + X + 
    1}, {X^5 + X^4 + X^3 + X^2 + 
    X + 1, X^6 + 1}, 
  {X^8 + X^7 + X^6 + X^2 + X + 1, 
   X^3 + 1}, {X^8 + X^4 + 1, 
   X^3 + X^2 + X + 1}, 
  {X^9 + X^8 + X^5 + X^4 + X + 1, 
   X^2 + 1}, {X^10 + X^8 + X^6 + 
    X^4 + X^2 + 1, X + 1}}];

I endeavoured to find less regular patterns. It might well have proven to be a wild goose chase, considering some of the theorems mentioned (and proved) by VUZA: his Thm 0.1 (about canons in ), and the nasty conditions related to HAJÒS's theorem. For "polynomial canons" of the kind I mention will, if irregular enough, generate a Vuza-canon ('regular complementary of maximal category', if I remember the phrasing aright. I will suggest a new word and a new concept later.). I confess the computer did most of the job. More later about what SHOULD be (should have been ?) done.

Irregular canons / canons irréguliers (non métronomiques)

The condition is to exclude either factor being of the kind
             
— what I would call a 'metronome', or a 'regular beat', or a 'bore'. There would be algebraic manipulations to be done, but the computer was doing well.
I hope these canons will prove of particular interest to composers, especially minimalist ones. The main difference with the 'usual' ones is that they are better packed up: everything occurs during a single period, which compels the time-span of a pattern to be short, and hence more striking and unmistakable for the listener.

These canons occur for n=16,24,32,36,40,48,54,56,60,64,72,80,81,84,88,90,96,100,104,108,112,120,126…
It came as a pleasant surprise that there are a number of these at all; but they are (usually) too regular for musical use. Hence some further pruning had to made.

Irreducible canons / canons irréductibles

Let's remember Tom JOHNSON's problem, as expressed by Mr. TANGIAN: if is a polynom for the rhythmic pattern, then one considers an equation of the kind

where are unknown 0-1 polynomials.
This emphasizes the importance of COMPOSITION among polynomials in the weak ring. To follow through the idea of echoing the natural numbers in studying 0-1 polynomials (there I cannot but agree with Mr. Tangian), arises the question of irreducible 0-1 polynomials, that is to say is NOT decomposable as .
This condition is severe: all of the examples above of irregular canons feature a factor of the kind (though with aperiodic Q). So are all the Vuza canons I know of (usually one of the sets is 2-periodic) and a number of cyclotomic polynomials. I have tested for a number of without finding any instance of such a decomposition. Some should exist, but for rather large (and very composite) . Why composite ? Time to return towards HAJÒS's thm and VUZA canons.

Aperiodic canons / canons apériodiques

Definition & motivation

Consider this example of irregular canon ():

The only flaw is the second term being reducible as (else one would get a Vuza-canon by n-periodicity). One could (and will) broaden the condition supra to avoiding periodic factors , that is to say factors such as , [augmentations of shorter rhythms]. Now for a move in the right direction:

Prop. If then at most one of P,Q is periodic.

Proof: if not, then .  —R

Definition: an aperiodic canon of length n will be a factorization of with P,Q being 0-1 aperiodic polynomials.
This is a special case of irreducible polynomials as defined above.

Some results about aperiodic canons.

First note that any aperiodic canon expands into something very much like a Vuza-canon under the wording of his thms 2.1 & 2.2. Hence (from Hajòs' theorems) a number of cases should be impossible. Indeed I have proven for a number of these cases, listed below,  that no aperiodic canon exists. This is not logically necessary, but gives useful insight into the reasons of these (for me) weird hypotheses. The general sentence begins with:

There is no aperiodic canon of length n when:

is a power of a prime.

is a product of two primes.

.

.

A useful Lemma for some of the proofs is

… is p-periodic ().

Just one proof as an example. One of the main points I  wish to make is that consideration of cyclotomics helps understand what is going on.

The Lemma stems from the formula with the Möbius function:

The proof for is a discussion of cases.

As , and it remains do discuss how this irreducible factors are distributed in two terms:  , with and aperiodic.
Consider the factor : it cannot be one of the terms A, B as . Say the first factor is : then the other one must be .
Hence it must be paired with one of , , or both. Notice first that
. This cannot be either or (it's a bore).
Still or will have 2 and 3 factors each. Say has 2 and has 3 and look for :
★ : but this is a bore - excluded.
★ × : this is -periodic as product of two -periodic polynomials.
★ : this is , hence not in ℵ.
By exhaustion of cases,  a proper factorization is impossible  —R.

What next ? / Et maintenant ?

—%  Most of the following is rather conjectural and shaky.

Vuza-canons as (universal ?) coverings

Vuza canons from 0-1 polynomials.

It is (strangely enough) possible to quotient the weak ring ℵ modulo polynomials that are not part of it. Not all 0-1 polynomials will survive the treatment, of course. For instance (example in [A]) the following derivation proves that there is a Vuza-canon for :

Now for a transformation rule:

vu /. X^n_ -> X^Mod[n, 72]

This is a quotient modulo . Generally,
Proposition. There exists a Vuza-canon of order iff there is a 0-1 polynomial (of large enough degree) which admits to a decomposition of the form
with being 0-1 polys.

Proof : easy. For a term in , just write

and sum (the 's will exactly span [0,n-1] on a one-to-one basis, by hypothesis).

In the example above,

Quotienting factorizations

In order to understand the link between economic canons and Vuza canons, I tried (experimentally) to quotient the factors. Two examples will show what may happen:

A = X^34 + X^26 + X^18 + X^16 + X^8 + 1; 
B = X^53 + X^49 + X^48 + X^42 + X^36 + X^29 + X^25 + 
    X^12 + X^6 + X^5 + X + 1; 
quo = X^n_ -> X^Mod[n, 24]; 
(A /. quo)*(B /. quo)

Failure ! Next try:

This is a factorization of (hence a rather trivial one): .
When does this occur ? Why ? What is exactly the relationship between my canons and the others ?

Aperiodic canons

Are there any out there ?

It IS possible that none exists, though I am inclined to doubt that. If so, a proof would doubtless be interesting and even give some insight on (the) other types of canons.

Find' em all !

By more theoretical research.
For instance I have not yet rounded up the last cases of Hajòs theorem (…and all cases with 3 or 4 prime factors) in the special case of aperiodic economical canons and I suggest it would be well worth the effort, as giving insight on why some (aperiodic) canons are impossible.
There are many threads I have left unexplored, for lack of time. I won't enumerate them now for the same reason.
Also a thorough study of the weak ring ℵ must be interesting by itself.

Improve the search/ improve the algorithm.
Theorical considerations might lead to more efficient tree-pruning and/or sieving. Is not the parallelism between the prime numbers (found by Eratosthenes' sieve, as it inspired M. Tangian) and the cyclotomic polynomials striking ? Indeed it is what induced me to initiate this research in the first place !

Make music with them

It would be worthwhile to develop a composer-friendly interface with 0-1 polys (the whole ℵ of them), cyclotomics and all, allowing composers to create their own economical canons. It should be ripe for OpenMusic v. 14.2 !