Xenharmonic Wiki

Generator preimage: Difference between revisions

← Older edit
VisualWikitext
Cmloegcmluin (talk | contribs)
autopatrolled, emailconfirmed
5,170 edits
remove temporary link to defactoring
Sintel (talk | contribs)
autopatrolled, emailconfirmed
1,632 edits
m typo again
 
(22 intermediate revisions by 4 users not shown)
Line 1: Line 1:
For each [[generator]] of a [[regular temperament]], we can choose one JI interval that maps to it. Then we can call a set of JI generators like this '''transversal generators''' of that temperament.
Also known as a '''generator preimage transversal''' or a '''generator [[detempering]]'''. Every [[generator]] of a [[regular temperament]] has a [[preimage]], which is an infinite set of JI intervals that map to it. A [[transversal]] means a selection of one representative element from each of a list of sets. So if for each generator in our temperament's list of generators we choose one JI interval that maps to it, then we have a generator preimage transversal for that temperament.


=Definition=
Generator preimages are commonly used to describe temperaments. For example, [[meantone]] is generated by an octave and fifth, and the corresponding generator preimage is [[2/1]] and [[3/2]]. [[Miracle]] is generated by an octave and a semitone, corresponding to [[2/1]] and [[16/15]]~[[15/14]].
Given a reduced list of [[Harmonic_Limit|p-limit]] vals V, we may define a set of transversal generators for V as a set of p-limit intervals q such that one of the vals of V maps q to 1 and the rest map it to 0. By ''reduced'' is meant that the gcd of the elements of each of the vals is 1--or in other words, none of the vals are [[contorted]]--and that they are linearly independent, so that if there are r vals, the rank of V as a matrix is r.
 
=Technical Definition=
Given a reduced list of [[Harmonic_Limit|p-limit]] vals V, we may define a set of transversal generators for V as a set of p-limit intervals q such that one of the vals of V maps q to 1 and the rest map it to 0. By ''reduced'' is meant that the GCD of the elements of each of the vals is 1--or in other words, none of the vals are [[contorted]]--and that they are [[linearly independent]], so that if there are r vals, the rank of V as a matrix is r.


If v1, v2, ... vr are the vals of V and t1, t2, ... tr are the corresponding transversal generators, then for any p-limit q we have, modulo the regular temperament defined by V
If v1, v2, ... vr are the vals of V and t1, t2, ... tr are the corresponding transversal generators, then for any p-limit q we have, modulo the regular temperament defined by V
Line 8: Line 10:
q ≅ t1^v1(q) * t2^v2(q) * ... * tr^vr(q)
q ≅ t1^v1(q) * t2^v2(q) * ... * tr^vr(q)


In this way the transversal generators provide a [[Transversal|transversal]] of the p-limit, and hence the name.
In this way the transversal generators provide a transversal of the p-limit, and hence the name.


=Examples=
=Examples=
Line 21: Line 23:
For another example, consider [<1 1 1 2|, <0 2 1 1|, <0 0 2 1|] which is the [[Normal_lists|normal val list]] for breed temperament, the temperament tempering out 2401/2400. A corresponding list of transversal generators is [2, 49/40, 10/7].
For another example, consider [<1 1 1 2|, <0 2 1 1|, <0 0 2 1|] which is the [[Normal_lists|normal val list]] for breed temperament, the temperament tempering out 2401/2400. A corresponding list of transversal generators is [2, 49/40, 10/7].


=Finding the transversal generators=
=Finding the generator preimage transversal=
We can find transveral generators for V by the following procedure:
{{todo|cleanup|inline=1|text=Add simpler algorithm}}
 
Two methods for finding the generator preimage transversal have been developed. The first was developed by [[Gene Ward Smith]] sometime in or before June 2011, which uses the [[Hermite normal form]]. The second was developed by [[User:Sintel|Sintel]] in December 2021, which uses the [[Smith normal form]].
 
== Method using the Smith Normal Form ==
 
So we want to find a generator preimage transversal <math>T</math> for a mapping <math>M</math> where:
 
 
<math>MT = I,</math>
 
 
and where <math>I</math> is the identity matrix. When this is the case, then for each generator of the temperament represented by <math>M</math>, a different column of <math>T</math> as a [[prime-count vector]] represents an interval that <math>M</math> maps to that generator. And when this <math>T</math> has all integer entries, then these generators are all JI.
 
Essentially we need a way to do:
 
 
<math>
M^{-1}MT = M^{-1}I \\
\cancel{M^{-1}M}T = M^{-1}I \\
T = M^{-1}
</math>
 
 
But there's two major problems with this simplistic approach:
# <math>M</math> is rectangular and therefore cannot be inverted (it has no inverse).
# The pseudoinverse we use in lieu of a true inverse in situations like this doesn't generally give integer results, and so it won't give us the JI generators we seek.
So the pseudoinverse won't solve this problem for us, but the Smith decomposition can help! For a given <math>M</math>, it finds invertible matrices <math>L</math> and <math>R</math> for which
 
 
<math>
LMR = D,
</math>
 
 
where <math>D</math> is the Smith Normal Form of <math>M</math>, which is a rectangular diagonal matrix (the name 'D' is for "diagonal"). Furthermore, if <math>M</math> was defactored, then not only is <math>D</math> diagonal (only has nonzero values along its main diagonal) but the numbers along its main diagonal are all equal to 1. This type of matrix is called an orthonormal matrix, and has the property that <math>D^{T}D = I</math>, which we're going to take advantage of.
 
So first let's solve the decomposition equation for <math>M</math>. First, left-multiply by <math>L^{-1}</math>:
 
 
<math>
L^{-1}LMR = L^{-1}D \\
\cancel{L^{-1}L}MR = L^{-1}D \\
MR = L^{-1}D
</math>
 
 
And then right-multiply by <math>R^{-1}</math>:
 
 
<math>
MRR^{-1} = L^{-1}DR^{-1} \\
M\cancel{RR^{-1}} = L^{-1}DR^{-1} \\
M = L^{-1}DR^{-1}
</math>
 
 
Now we can substitute this result in for <math>M</math> in our original equation:
 
 
<math>
(L^{-1}DR^{-1})T = I
</math>
 
 
And we can proceed to solve this for our target <math>T</math>. The rest is busywork. First, left-multiply by <math>L</math>:
 
 
<math>
LL^{-1}DR^{-1}T = LI \\
\cancel{LL^{-1}}DR^{-1}T = LI \\
DR^{-1}T = L
</math>
 
 
Then left-multiply by <math>D^{T}</math>:
 
 
<math>
D^{T}DR^{-1}T = D^{T}L \\
\cancel{D^{T}D}R^{-1}T = D^{T}L \\
R^{-1}T = D^{T}L
</math>
 
 
And finally, left-multiply by <math>R</math>:
 
 
<math>
RR^{-1}T = RD^{T}L \\
\cancel{RR^{-1}}T = RD^{T}L \\
T = RD^{T}L
</math>
 
 
And there's our answer! It's still not necessarily giving the simplest or best JI generators, but arriving at those is an independent problem (perhaps by choosing a complexity metric and minimizing it though linear combinations with the commas and the other generators, or perhaps using LLL).
 
=== Example ===
 
Our mapping is 5-limit meantone, in [[equave-reduced generator form]]:
 
 
<math>
\left[ \begin{array} {rrr}
1 & 1 & 0 \\
0 & 1 & 4 \\
\end{array} \right]
</math>
 
 
Its Smith Decomposition <math>L, D, R</math> is:
 
 
<math>
\begin{array} {lll}
 
\left[ \begin{array} {rrr}
1 & -1 \\
0 & 1 \\
\end{array} \right]
 
, &
 
\left[ \begin{array} {rrr}
1 & 0 & 0 \\
0 & 1 & 0 \\
\end{array} \right]
 
, &
 
\left[ \begin{array} {rrr}
1 & 0 & 4 \\
0 & 1 & -4 \\
0 & 0 & 1 \\
\end{array} \right]
 
\end{array}
</math>
 
 
And so a transversal of the preimages of its generators are <math>RD^{T}L</math>:
 
 
<math>
\left[ \begin{matrix}
1 & 0 & 4 \\
0 & 1 & -4 \\
0 & 0 & 1 \\
\end{matrix} \right]
\left[ \begin{matrix}
1 & 0 \\
0 & 1 \\
0 & 0 \\
\end{matrix} \right]
\left[ \begin{matrix}
1 & -1 \\
0 & 1 \\
\end{matrix} \right]
=
\left[ \begin{matrix}
1 & -1 \\
0 & 1 \\
0 & 0 \\
\end{matrix} \right]
</math>
 
 
That is, 2/1 and 3/2.
 
=== Wolfram Language implementation ===
 
{{Databox|getGpt[]|
<syntaxhighlight lang="mathematica">
getGpt[m_] := Module[{decomp, left, snf, right},
  decomp = SmithDecomposition[m];
  left = Part[decomp, 1];
  snf  = Part[decomp, 2];
  right = Part[decomp, 3];
 
  right.Transpose[snf].left
];
</syntaxhighlight>}}
 
== Method using the Hermite Normal Form ==
 
We can find a generator preimage transversal for V by the following procedure:


<ul><li>Take the transpose of the [[Tenney-Euclidean_Tuning#The pseudoinverse|pseudoinverse]] of V, call that U</li><li>Find a basis for the commas of V</li><li>For each row U[i] of U, clear denominators and append the monzos of the comma basis for V</li><li>[[Saturation|Saturate]] the result to a list of monzos, call that S</li><li>Apply the ith val V[i] (dot product) to each element of S</li><li>Insert V[i].S[j] in front of the elements of S[j] as the first element, obtaining the jth element T[j] of a modified list T</li><li>Hermite reduce the modified list T, take the first row, and remove the first element (which should be a 1.)</li><li>Consider the rest to be a monzo and convert it to a rational number</li><li>This is a corresponding transveral generator to the ith val V[i] of V; it may be reduced to an equivalent generator of minimal [[Tenney_Height|Tenney height]] by multiplying by the commas of V</li></ul>       
<ul><li>Take the transpose of the [[Tenney-Euclidean_Tuning#The pseudoinverse|pseudoinverse]] of V, call that U</li><li>Find a basis for the commas of V</li><li>For each row U[i] of U, clear denominators and append the monzos of the comma basis for V</li><li>[[Saturation|Saturate]] the result to a list of monzos, call that S</li><li>Apply the ith val V[i] (dot product) to each element of S</li><li>Insert V[i].S[j] in front of the elements of S[j] as the first element, obtaining the jth element T[j] of a modified list T</li><li>Hermite reduce the modified list T, take the first row, and remove the first element (which should be a 1.)</li><li>Consider the rest to be a monzo and convert it to a rational number</li><li>This is a corresponding transveral generator to the ith val V[i] of V; it may be reduced to an equivalent generator of minimal [[Tenney_Height|Tenney height]] by multiplying by the commas of V</li></ul>       


== Example ==
=== Example ===


Note: I've followed the algorithm as described above. But clearly I am transposing things here way more often than is necessary than if the algorithm was superficially revised.
Note: I've followed the algorithm as described above. But clearly I am transposing things here way more often than is necessary than if the algorithm was superficially revised.
Line 210: Line 397:
So indeed that gives the generator for meantone, 4/3. We're done!
So indeed that gives the generator for meantone, 4/3. We're done!


== Wolfram Language implementation ==
=== Wolfram Language implementation ===


{{Databox|transversalGenerators[]|
{{Databox|getGpt[]|
<syntaxhighlight lang="mathematica">
<syntaxhighlight lang="mathematica">
transversalGenerator[u_, v_, c_] := Module[{base},
getGptEntry[u_, v_, c_] := Module[{base},
   base = Transpose[columnHermiteDefactor[Join[{u}, Transpose[c]]]];
   base = Transpose[columnHermiteDefactor[Join[{u}, Transpose[c]]]];


Line 220: Line 407:
];
];


transversalGenerators[m_] := Module[{c},
getGptSmithMethod[m_] := Module[{c},
   c = nullSpaceBasis[m];
   c = nullSpaceBasis[m];
   Transpose[MapThread[transversalGenerator[#1, #1, c]&, {Map[multByLcd,Transpose[PseudoInverse[m]]],m}]]
   Transpose[MapThread[getGptEntry[#1, #1, c]&, {Map[multByLcd,Transpose[PseudoInverse[m]]],m}]]
];
];


transversalGenerators[{{1,2,4},{0,-1,-4}}] (* {{1,2},{0,-1},{0,0}} = 2/1 and 4/3 as expected *)
getGptSmithMethod[{{1,2,4},{0,-1,-4}}] (* {{1,2},{0,-1},{0,0}} = 2/1 and 4/3 as expected *)
</syntaxhighlight>}}
</syntaxhighlight>}}


[[Category:generator]]
[[Category:generator]]
[[Category:theory]]
[[Category:Regular temperament theory]]
[[Category:todo:reduce_mathslang]]
[[Category:todo:reduce_mathslang]]
Retrieved from "https://en.xen.wiki/w/Generator_preimage"