LLL reduction: Difference between revisions

Newer edit →

VisualWikitext

@@ Line 10: / Line 10: @@
 Since LLL reduction depends on the choice of inner product, we can use something like the [[Tenney-Euclidean norm|Tenney]] or [[Wilson height|Wilson]] norm to define the complexity we want to penalize.
-== Example of computing a comma basis ==
+Another application is finding good bases for JI that can be used as [[Fokker block]]s.
+== Computing the comma basis for a temperament ==
 Let's take 7-limit meantone as an example. The mapping matrix is:
 $$
@@ Line 54: / Line 56: @@
 This gives a comma basis of [[126/125]] and [[81/80]], which is what we expect for septimal meantone.
+== Computing Fokker blocks ==
+Consider some p-limit [[subgroup]], with the log-prime vector
+<math>j = \begin{bmatrix}
+\log_2 2 & \log_2 3 & \cdots & \log_2 p \\
+\end{bmatrix} </math>.
+Pick some value for k, and construct the following block matrix:
+$$
+\begin{bmatrix}
+\mathrm{I} \\
+\hline
+k \cdot \log_2 j
+\end{bmatrix}
+=
+\begin{bmatrix}
+& 0 & \cdots & 0 \\
+& 1 & \cdots & 0 \\
+\vdots & \vdots & \ddots & \vdots \\
+& 0 & \cdots & 1 \\
+\hline
+k \log_2(p_1) & k \log_2(p_2) & \cdots & k \log_2(p_n) &
+\end{bmatrix}
+$$
+(Note the similarity to the definition of the k-Weil-Euclidean norm.)
+After applying LLL reduction to the columns, and removing the last row, we are left with a square matrix that defines a change of basis.
+Since this basis is unimodular, we can invert it to obtain a dual basis containing EDO-maps.
+To give a concrete example, consider 7-limit JI, and pick (somewhat arbitrarily) k = 800. The matrix then looks like:
+$$
+\begin{bmatrix}
+\mathrm{I} \\
+\hline
+\cdot \log_2 j
+\end{bmatrix}
+=
+\begin{bmatrix}
+& 0 & 0 & 0 \\
+& 1 & 0 & 0 \\
+& 0 & 1 & 0 \\
+& 0 & 0 & 1 \\
+\hline
+& 1268 & 1858 & 2246 &
+\end{bmatrix}
+$$
+We can interpret the columns as consisting of intervals followed by their size. If we had picked k = 1200, the last row would be in cents.
+When LLL reducing this matrix, we are asking for columns that have small coefficients, as well as small spans, which is what we want for nice commas!
+The choice of parameter k will set the tradeoff between the span and complexity, larger k giving smaller but more complex commas.
+The reduced basis is:
+$$
+\begin{bmatrix}
+\mathrm{B} \\
+\hline
+u
+\end{bmatrix}
+=
+\begin{bmatrix}
+-5 &  6 & -5 & -1 \\
+-1 &  0 &  2 & -7 \\
+-2 & -5 &  2 &  4 \\
+  &  2 & -1 &  1 \\
+\hline
+& 2 & 6 & 2
+\end{bmatrix}
+$$
+Throwing away the bottom row, we are left with a square matrix <math>\mathrm{B}</math>.
+Reading off the columns as prime-count vectors, we get:
+* <math>2^{-5} \cdot 3^{-1} \cdot 5^{-2} \cdot 7^{4} = </math> [[2401/2400]], the breedsma.
+* <math>2^{6}  \cdot             5^{-5} \cdot 7^{2} = </math> [[3136/3125]], the didacus comma.
+* <math>2^{-5} \cdot 3^{2} \cdot 5^{2} \cdot 7^{-1} = </math> [[225/224]], the marvel comma.
+* <math>2^{-1} \cdot 3^{-7} \cdot 5^{4} \cdot 7 = </math> [[4375/4374]], the ragisma.
+Because we started with the identity matrix, this block is guaranteed have <math>\left| \mathrm{B} \right| = 1</math> so we can invert it in the integers.
+$$
+\mathrm{B}^{-1} =
+\begin{bmatrix}
+&  30 &  44 &  53 \\
+& 114 & 167 & 202 \\
+& 157 & 230 & 278 \\
+&  49 &  72 &  87 \\
+\end{bmatrix}
+$$
+The rows of this matrix are the 7-limit maps of 19-EDO, 72-EDO, 99-EDO and 31-EDO.
+Of course, this matrix is also unimodular, so it defines a change of basis in the dual space.
+Because they are inverses, these two bases have the property that for each EDO, the corresponding comma is mapped to 1 step, and all the other commas are tempered out.
+For example, 31-EDO maps the ragisma to one step, and tempers out the breedsma, didacus and marvel comma. In fact, 31-EDO is the unique EDO tempering out these three commas in the 7 limit.