Gral method

The Gral method is a method used by Erv Wilson for keyboard mapping and finding moments of symmetry.

Lattice bases

For concreteness, consider a two-dimensional keyboard. The keys on the keyboard are labeled by pairs of integers [math]\displaystyle{ (x, y) }[/math], their [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] coordinates. The set of all these integer pairs is called a lattice. For two lattice points [math]\displaystyle{ (a, b) }[/math] and [math]\displaystyle{ (c, d) }[/math], if we can write any lattice point [math]\displaystyle{ (x, y) }[/math] as

[math]\displaystyle{ \displaystyle \begin{bmatrix} x \\ y \\ \end{bmatrix} = p \begin{bmatrix} a \\ b \\ \end{bmatrix} + q \begin{bmatrix} c \\ d \\ \end{bmatrix} }[/math]

with integer [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math], we say [math]\displaystyle{ (a, b) }[/math] and [math]\displaystyle{ (c, d) }[/math] form a basis for the lattice. Two points [math]\displaystyle{ (a, b) }[/math] and [math]\displaystyle{ (c, d) }[/math] form a basis if and only if [math]\displaystyle{ ad - bc = \pm 1 }[/math].

Problem

Figure 1: Lattice geometry for the Gral method.

Say we have a lattice with points [math]\displaystyle{ (x, y) }[/math]. Consider a quantity [math]\displaystyle{ q }[/math] which depends linearly on [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math], so

[math]\displaystyle{ q = s x + t y }[/math]

for some step sizes [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math].

Given two numbers [math]\displaystyle{ g }[/math] and [math]\displaystyle{ h }[/math], we are looking for a lattice basis [math]\displaystyle{ (a, b) }[/math], [math]\displaystyle{ (c, d) }[/math] such that the value of [math]\displaystyle{ q }[/math] is [math]\displaystyle{ g }[/math] at [math]\displaystyle{ (a, b) }[/math] and [math]\displaystyle{ h }[/math] at [math]\displaystyle{ (c, d) }[/math], that is

[math]\displaystyle{ \displaystyle \begin{align} g &= a s + b t \\ h &= c s + d t \end{align} }[/math]

and for which the step sizes [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] are positive.

The step sizes are determined by the numbers [math]\displaystyle{ g }[/math], [math]\displaystyle{ h }[/math] and the basis [math]\displaystyle{ (a, b) }[/math], [math]\displaystyle{ (c, d) }[/math] as

[math]\displaystyle{ \displaystyle \begin{align} s &= \frac{dg - bh}{\Delta} \\ t &= \frac{-cg + ah}{\Delta} \\ \end{align} }[/math]

where [math]\displaystyle{ \Delta = ad - bc }[/math], and [math]\displaystyle{ \Delta = \pm 1 }[/math] since [math]\displaystyle{ (a, b) }[/math], [math]\displaystyle{ (c, d) }[/math] is a lattice basis.

If [math]\displaystyle{ \Delta = -1 }[/math], [math]\displaystyle{ c > 0 }[/math], and [math]\displaystyle{ d > 0 }[/math], the positive step size conditions [math]\displaystyle{ s > 0 }[/math], [math]\displaystyle{ t > 0 }[/math] are equivalent to

[math]\displaystyle{ \displaystyle \frac{a}{c} < \frac{g}{h} < \frac{b}{d} }[/math]

Figure 1 shows the problem setup geometrically.

Algorithm

Given numbers [math]\displaystyle{ g }[/math] and [math]\displaystyle{ h }[/math], the Gral method finds all lattice bases [math]\displaystyle{ (a, b) }[/math], [math]\displaystyle{ (c, d) }[/math] such that

• [math]\displaystyle{ ad - bc = -1 }[/math]
• [math]\displaystyle{ a, b, c, d \geq 0 }[/math]
• [math]\displaystyle{ \frac{a}{c} < \frac{g}{h} < \frac{b}{d} }[/math]

The algorithm is a binary search for the number [math]\displaystyle{ g/h }[/math], starting with the interval [math]\displaystyle{ [0/1, 1/0] }[/math] and 'bisecting' each interval [math]\displaystyle{ [a/c, b/d] }[/math] with the mediant [math]\displaystyle{ (a+b)/(c+d) }[/math]. Each interval [math]\displaystyle{ [a/c, b/d] }[/math] we encounter in the search has [math]\displaystyle{ ad - bc = -1 }[/math], so [math]\displaystyle{ (a, b) }[/math], [math]\displaystyle{ (c, d) }[/math] form a basis, and [math]\displaystyle{ a/c < g/h < b/d }[/math] since [math]\displaystyle{ g/h }[/math] is in each search interval.

Application to finding MOS

The Gral method finds all MOS formed when stacking a generator of pitch [math]\displaystyle{ g }[/math] cents within a period of pitch [math]\displaystyle{ h }[/math] cents. Applying the Gral method to [math]\displaystyle{ g }[/math] and [math]\displaystyle{ h }[/math], each interval [math]\displaystyle{ [a/c, b/d] }[/math] found gives a MOS with [math]\displaystyle{ n = c + d }[/math] notes, where the generator is at scale degree [math]\displaystyle{ m = a + b }[/math]; call this an [math]\displaystyle{ m/n }[/math] MOS.

• The step sizes [math]\displaystyle{ s = -d g + b h }[/math] and [math]\displaystyle{ t = c g - a h }[/math] are the MOS step sizes.
• The MOS has [math]\displaystyle{ c }[/math] steps of [math]\displaystyle{ s }[/math] and [math]\displaystyle{ d }[/math] steps of [math]\displaystyle{ t }[/math].
• The interval [math]\displaystyle{ [a/c, b/d] }[/math] gives the range of [math]\displaystyle{ g/h }[/math] which will produce an [math]\displaystyle{ m/n }[/math] MOS when stacking.

In this way the Gral method directly gives the generator range and step size formulae from the Generator ranges of MOS page.

For example, take [math]\displaystyle{ g = 707.22 }[/math] cents and [math]\displaystyle{ h = 1200 }[/math] cents. The Gral method can usefully be shown in a table as follows:

Left	Right	Mediant	[math]\displaystyle{ a }[/math]	[math]\displaystyle{ b }[/math]	[math]\displaystyle{ c }[/math]	[math]\displaystyle{ d }[/math]	[math]\displaystyle{ s }[/math]	[math]\displaystyle{ t }[/math]
0/1	1/0	1/1	0	1	1	0	1200.00	707.22
	1/1	1/2	0	1	1	1	492.78	707.22
1/2		2/3	1	1	2	1	492.78	214.44
	2/3	3/5	1	2	2	3	278.34	214.44
	3/5	4/7	1	3	2	5	63.90	214.44
4/7		7/12	4	3	7	5	63.90	150.54
7/12		10/17	7	3	12	5	63.90	86.64
10/17		13/22	10	3	17	5	63.90	22.74
	13/22	23/39	10	13	17	22	41.16	22.74
	23/39	33/56	10	23	17	39	18.42	22.74
33/56		56/95	33	23	56	39	18.42	4.32

Here Left and Right are the endpoints of the search interval; a blank means the same value as the row above (this lets you see at a glance which endpoint moved to form each row). The Mediant column is the mediant of the search interval. The columns a, b, c, d give the basis [math]\displaystyle{ (a,b) }[/math], [math]\displaystyle{ (c,d) }[/math] corresponding to the search interval [math]\displaystyle{ [a/c,b/d] }[/math]. The columns s and t give the resulting step sizes (for which [math]\displaystyle{ as+ bt = g }[/math] and [math]\displaystyle{ cs + dt = h }[/math]).

The row with mediant 10/17, for example, tells us that we get a 17 note MOS with 12 steps of 63.90 cents and 5 steps of 86.64 cents. The corresponding search interval [math]\displaystyle{ [7/12, 3/5] }[/math] tells us that any generator [math]\displaystyle{ g }[/math] between [math]\displaystyle{ 1200 \cdot 7/12 = 700 }[/math] cents and [math]\displaystyle{ 1200 \cdot 3/5 = 720 }[/math] cents will give a 10/17 MOS.

The Gral method is a very convenient way to calculate MOS, and it was extensively used by Wilson. We can understand why the Gral method calculates MOS by thinking about keyboard mapping.

Application to keyboard mapping

One way to map a scale onto a two-dimensional keyboard is to always go up [math]\displaystyle{ s }[/math] scale degrees when moving one key along a row, and [math]\displaystyle{ t }[/math] scale degrees when moving one key up a column, for some step sizes [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math]. If we choose scale degrees [math]\displaystyle{ m }[/math] and [math]\displaystyle{ n }[/math] which we want to be mapped to a basis on the keyboard, the Gral method applied with [math]\displaystyle{ g = m }[/math] and [math]\displaystyle{ h = n }[/math] tells us which bases with non-negative coordinates will give positive step sizes [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math].

For example, if we want scale degrees [math]\displaystyle{ m = 11 }[/math] and [math]\displaystyle{ n = 19 }[/math] to be mapped to a basis on the keyboard, we can apply the Gral method to 11 and 19:

Left	Right	Mediant	[math]\displaystyle{ a }[/math]	[math]\displaystyle{ b }[/math]	[math]\displaystyle{ c }[/math]	[math]\displaystyle{ d }[/math]	[math]\displaystyle{ s }[/math]	[math]\displaystyle{ t }[/math]
0/1	1/0	1/1	0	1	1	0	19	11
	1/1	1/2	0	1	1	1	8	11
1/2		2/3	1	1	2	1	8	3
	2/3	3/5	1	2	2	3	5	3
	3/5	4/7	1	3	2	5	2	3
4/7		7/12	4	3	7	5	2	1
	7/12	11/19	4	7	7	12	1	1

The row with mediant 4/7, for example, tells us that mapping the scale by going up 2 scale degrees when moving along a row and 3 scale degrees when moving up a column will place scale degree 11 at [math]\displaystyle{ (1, 3) }[/math] and scale degree 19 at [math]\displaystyle{ (2, 5) }[/math]. Wilson describes each basis as a different keyboard named with the mediant, so the basis [math]\displaystyle{ (1, 3) }[/math], [math]\displaystyle{ (2, 5) }[/math] is called the 4/7 keyboard.

Labeling the MOS

For a given interval [math]\displaystyle{ [a/c, b/d] }[/math] found by the Gral method, we might label the corresponding MOS by either of

• The mediant [math]\displaystyle{ m/n = (a + b)/(c + d) }[/math]
• The step counts [math]\displaystyle{ c }[/math] and [math]\displaystyle{ d }[/math]

So for the MOS corresponding to the row with mediant 10/17 discussed above, we might call it a 10/17 MOS, or a 12[math]\displaystyle{ s }[/math] 5[math]\displaystyle{ t }[/math] MOS. We can convert between these two labels:

• Given the mediant [math]\displaystyle{ m/n }[/math], we have [math]\displaystyle{ c = m^{-1}\ (\mathrm{mod}\ n) }[/math] and [math]\displaystyle{ d = n - c }[/math].
• Given the step counts [math]\displaystyle{ c }[/math] and [math]\displaystyle{ d }[/math], we have [math]\displaystyle{ n = c + d }[/math] and [math]\displaystyle{ m = c^{-1}\ (\mathrm{mod}\ n) }[/math].

Here [math]\displaystyle{ m = c^{-1}\ (\mathrm{mod}\ n) }[/math] means [math]\displaystyle{ m }[/math] is the modular inverse of [math]\displaystyle{ c }[/math] with respect to [math]\displaystyle{ n }[/math]; in Python this is written m = pow(c, -1, n). The modular inverse comes up because [math]\displaystyle{ ad - bc = -1 }[/math] is equivalent to [math]\displaystyle{ cm - an = 1 }[/math], so [math]\displaystyle{ cm \equiv 1\ (\mathrm{mod}\ n) }[/math].