LLL reduction

English Wikipedia has an article on:

Lenstra–Lenstra–Lovász lattice basis reduction algorithm

The LLL (Lenstra–Lenstra–Lovász) reduction is an algorithm that computes a basis with short, nearly orthogonal vectors when given an integer lattice. Although determining the 'best' basis is an NP-complete problem^{[citation needed]}, the LLL algorithm can find a good basis in polynomial time.

Applications

The most obvious application of LLL reduction is finding a good comma basis for some abstract temperament. When computing the kernel of a temperament, the commas define a lattice. Applying LLL reduction to this lattice finds a new basis where all commas are short. Note that 'short' with respect to a suitable norm here means really means 'simple'. Since LLL reduction depends on the choice of inner product, we can use something like the Tenney or Wilson norm to define the complexity we want to penalize.

Another application is finding good bases for JI that can be used as Fokker blocks.

Computing the comma basis for a temperament

Let's take 7-limit meantone as an example. The mapping matrix is: $$ \begin{eqnarray} \left[ \begin{array}{rrrr} 1 & 0 & -4 & 13 \\ 0 & 1 & 4 & 10 \end{array} \right] \end{eqnarray} $$

When computing the kernel of this map (using e.g. the Hermite normal form), we get: $$ \begin{eqnarray} \left[ \begin{array}{rrr} 1 & 0 \\ 2 & 12 \\ -3 & -13 \\ 1 & 4 \end{array} \right] \end{eqnarray} $$

Reading off the columns of this matrix, these give [math]\displaystyle{ 2 \cdot 3^{2} \cdot 5^{-3} \cdot 7 = }[/math] 126/125 and [math]\displaystyle{ 3^{12} \cdot 5^{-13} \cdot 7^{4} = }[/math] 1275989841/1220703125, which is probably not what we want.

Applying LLL reduction to the columns of this matrix gives: $$ \begin{eqnarray} \left[ \begin{array}{rrr} 1 & -4 \\ 2 & 4 \\ -3 & -1 \\ 1 & 0 \end{array} \right] \end{eqnarray} $$

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]\displaystyle{ 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 j \end{bmatrix} = \begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \\ \hline k \log_2(2) & k \log_2(3) & \cdots & k \log_2(p) & \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 800 j \end{bmatrix} = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \hline 800 & 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 \\ 4 & 2 & -1 & 1 \\ \hline 0 & 2 & 6 & 2 \end{bmatrix} $$

Throwing away the bottom row, we are left with a square matrix [math]\displaystyle{ \mathrm{B} }[/math]. Reading off the columns as prime-count vectors, we get:

• [math]\displaystyle{ 2^{-5} \cdot 3^{-1} \cdot 5^{-2} \cdot 7^{4} = }[/math] 2401/2400, the breedsma.
• [math]\displaystyle{ 2^{6} \cdot 5^{-5} \cdot 7^{2} = }[/math] 3136/3125, the didacus comma.
• [math]\displaystyle{ 2^{-5} \cdot 3^{2} \cdot 5^{2} \cdot 7^{-1} = }[/math] 225/224, the marvel comma.
• [math]\displaystyle{ 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]\displaystyle{ \left| \det (\mathrm{B}) \right| = 1 }[/math] so we can invert it in the integers. $$ \mathrm{B}^{-1} = \begin{bmatrix} 19 & 30 & 44 & 53 \\ 72 & 114 & 167 & 202 \\ 99 & 157 & 230 & 278 \\ 31 & 49 & 72 & 87 \\ \end{bmatrix} $$

The rows of this matrix are the 7-limit maps of 19edo, 72edo, 99edo and 31edo. 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, 31edo maps the ragisma to one step, and tempers out the breedsma, didacus and marvel comma. In fact, 31edo is the unique EDO tempering out these three commas in the 7-limit.