Xenharmonic Wiki

Recursive structure of MOS scales: Difference between revisions

← Older editNewer edit →
VisualWikitext
Inthar (talk | contribs)
autopatrolled
15,004 edits
No edit summary
Inthar (talk | contribs)
autopatrolled
15,004 edits
My recent edits prematurely assumed that the reduced MOS was generated.
Line 1: Line 1:
By looking at the "tetrachords" L…s of an [[MOS scale]] (here MOS is defined as 'maximum variety 2') in word form and giving them the names "L" and "s", we get out another MOS scale. The MOS thus obtained preserves a number of important properties, such as which interval is the generator. To find properties of complex MOS word patterns, we can then just compare them to the simpler ones, whose properties we know.
By looking at the "tetrachords" L…s of an MOS scale in word form and giving them the names "L" and "s", we get out another MOS scale. The MOS thus obtained preserves a number of important properties, such as which interval is the generator. To find properties of complex MOS word patterns, we can then just compare them to the simpler ones, whose properties we know.


== Recursive structure ==
== Recursive structure ==
Line 16: Line 16:
* There is a third special case where there is exactly one L and one s in the scale, producing "Ls" or "sL". Technically speaking, it's possible to reduce the previous two special cases even further into this special case.
* There is a third special case where there is exactly one L and one s in the scale, producing "Ls" or "sL". Technically speaking, it's possible to reduce the previous two special cases even further into this special case.


In both case 1 and 2, the L's and s's are distributed in a MOS way, but the chunks of L's and s's are arranged so that they too form a MOS. This can be demonstrated by reducing the larger chunks into L and the smaller chunks into s. This produces a new scale W that is also a moment-of-symmetry scale. This process can be repeated multiple times until the scale is reduced into one of the special cases. In case 3, it is possible to reduce a multi-period scale until it consists of a single unique MOS-like chunk repeated c times, where that chunk is one of the special cases.
In both case 1 and 2, the L's and s's are distributed such that they are maximally even (that is, they are distributed as evenly as possible), but the chunks of L's and s's are arranged so that they too are maximally even. This can be demonstrated by reducing the larger chunks into L and the smaller chunks into s. This produces a new scale W that is also a moment-of-symmetry scale. This process can be repeated multiple times until the scale is reduced into one of the special cases. In case 3, it is possible to reduce a multi-period scale until it consists of a single unique MOS-like chunk repeated c times, where that chunk is one of the special cases.


Note that in this reduction process, the order of L's and s's may reverse. This is normal.
Note that in this reduction process, the order of L's and s's may reverse. This is normal.
Line 37: Line 37:


==== Stepwise version ====
==== Stepwise version ====
This is the general algorithm for determining whether a binary scale is a valid MOS. This version of the algorithm that uses the production rules in reverse: L -> Ls and s ->s; and L -> sL and s -> L. It is required to perform this on the string that represents the scale in its brightest mode. This algorithm is recursive.
This is the general algorithm for determining whether a scale is maximally even (that is, it is a valid MOS). This version of the algorithm that uses the production rules in reverse: L -> Ls and s ->s; and L -> sL and s -> L. It is required to perform this on the string that represents the scale in its brightest mode. This algorithm is recursive.


# Count how many L's and s's there are within the string. Let x be the number of L's and y be the number of s's. One of two situations will happen:
# Count how many L's and s's there are within the string. Let x be the number of L's and y be the number of s's. One of two situations will happen:
## If both x and y are equal to 1, then the scale is MOS.
## If both x and y are equal to 1, then the scale is maximally even.
## If x and y share a common factor k (that is, x and y are not coprime), then the scale is a multi-period scale. Split the string into k substrings that are exactly (x+y)/k characters long. If all of the substrings are identical, then perform the algorithm corresponding to that substring to determine whether the substring is MOS. If it's not the case that all of the substrings are identical or the substring is not MOS, then the scale is not MOS.
## If x and y share a common factor k (that is, x and y are not coprime), then the scale is a multi-period scale. Split the string into k substrings that are exactly (x+y)/k characters long. If all of the substrings are identical, then perform the algorithm corresponding to that substring to determine whether the substring is maximally even. If it's not the case that all of the substrings are identical or the substring is not maximally even, then the scale is not maximally even.
# If there are more L's than s's AND there are either at least two adjacent s's or an s is at the beginning and end of the string, then scale is not MOS. If there are more s's than L's AND there are either at least two adjacent L's or an L is at the beginning and end of the string, then the scale is not MOS. This is because between every two instances of the character that appears the least must be at least one instance of the character that appears the most; this also applies if the character that appears the least appears at both ends of the string, as a different mode of the same string will put those two characters next to another.
# If there are more L's than s's AND there are either at least two adjacent s's or an s is at the beginning and end of the string, then scale is not maximally even. If there are more s's than L's AND there are either at least two adjacent L's or an L is at the beginning and end of the string, then the scale is not maximally even. This is because between every two instances of the character that appears the least must be at least one instance of the character that appears the most; this also applies if the character that appears the least appears at both ends of the string, as a different mode of the same string will put those two characters next to another.
# Split the string into a sequence of chunks as described: if there are more L's than s's (or if x > y), then each chunk will consist of at least one L followed by exactly one s; if instead there are more s's than L's (or y > x), then each chunk will consist of exactly one L followed by at least one s. Preserve the order of these chunks.
# Split the string into a sequence of chunks as described: if there are more L's than s's (or if x > y), then each chunk will consist of at least one L followed by exactly one s; if instead there are more s's than L's (or y > x), then each chunk will consist of exactly one L followed by at least one s. Preserve the order of these chunks.
# Count how many UNIQUE chunks there are. If there are more than two unique strings, then the scale is not MOS. If there are only two unique strings but their lengths differ by more than 1, then the scale is not MOS.
# Count how many UNIQUE chunks there are. If there are more than two unique strings, then the scale is not maximally even. If there are only two unique strings but their lengths differ by more than 1, then the scale is not maximally even.
# If there are more L's than s's, then for each chunk, replace all but the last two characters with s's, and replace the last two characters with a single L. This process represents L->sL and s->L. If there are more s's than L's, then for each chunk, replace only the first two characters with a single L. This process represents L->Ls and s->s, but reversed. The scale produced this way is the parent scale.
# If there are more L's than s's, then for each chunk, replace all but the last two characters with s's, and replace the last two characters with a single L. This process represents L->sL and s->L. If there are more s's than L's, then for each chunk, replace only the first two characters with a single L. This process represents L->Ls and s->s, but reversed. The scale produced this way is the parent scale.
# Repeat the algorithm recursively on the parent scale. If that scale is MOS, then the original scale is MOS.
# Repeat the algorithm recursively on the parent scale. If that scale is maximally even, then the original scale is maximally even.


==== Chunking version ====
==== Chunking version ====
This is the general algorithm for determining whether a binary scale is MOS (that is, it is a valid MOS). This version of the algorithm reduces entire chunks into L's and s's based on the size of the chunks. It is recommended, but not required, to perform this on the string representing the scale in either its brightest or darkest mode. This algorithm is recursive.
This is the general algorithm for determining whether a scale is maximally even (that is, it is a valid MOS). This version of the algorithm reduces entire chunks into L's and s's based on the size of the chunks. It is recommended, but not required, to perform this on the string representing the scale in either its brightest or darkest mode. This algorithm is recursive.


# Count how many L's and s's there are within the string. Let x be the number of L's and y be the number of s's. One of two situations will happen:
# Count how many L's and s's there are within the string. Let x be the number of L's and y be the number of s's. One of two situations will happen:
## If either x or y is equal to 1, or both x and y are equal to 1, then the scale is MOS.
## If either x or y is equal to 1, or both x and y are equal to 1, then the scale is maximally even.
## If x and y share a common factor k (that is, x and y are not coprime), then the scale is a multi-period scale. Split the string into k substrings that are exactly (x+y)/k characters long. If all of the substrings are identical, then perform the algorithm corresponding to that substring to determine whether the substring is MOS. If it's not the case that all of the substrings are identical or the substring is not MOS, then the scale is not MOS.
## If x and y share a common factor k (that is, x and y are not coprime), then the scale is a multi-period scale. Split the string into k substrings that are exactly (x+y)/k characters long. If all of the substrings are identical, then perform the algorithm corresponding to that substring to determine whether the substring is maximally even. If it's not the case that all of the substrings are identical or the substring is not maximally even, then the scale is not maximally even.
# If there are more L's than s's AND there are either at least two adjacent s's or an s is at the beginning and end of the string, then scale is not MOS. If there are more s's than L's AND there are either at least two adjacent L's or an L is at the beginning and end of the string, then the scale is not MOS. This is because between every two instances of the character that appears the least must be at least one instance of the character that appears the most; this also applies if the character that appears the least appears at both ends of the string, as a different mode of the same string will put those two characters next to another.
# If there are more L's than s's AND there are either at least two adjacent s's or an s is at the beginning and end of the string, then scale is not maximally even. If there are more s's than L's AND there are either at least two adjacent L's or an L is at the beginning and end of the string, then the scale is not maximally even. This is because between every two instances of the character that appears the least must be at least one instance of the character that appears the most; this also applies if the character that appears the least appears at both ends of the string, as a different mode of the same string will put those two characters next to another.
# Split the string into a sequence of chunks, not by splitting the strings into chunks that contain L's and s's, but AT the character that appears the least. Because every chunk contains at least one L and at least one s, removing the character that appears the least will not make any difference to how the chunks are ordered in terms of size. If there are more L's than s's, then there should be exactly y chunks consisting of only L's, and if there are more s's than L's, then there should be exactly x chunks consisting of only s's. If there is exactly one more string than expected, this may be because the string was in a mode that split one of the chunks into two; in this case, combine the first and last chunks in the sequence back into one chunk to get the correct number of chunks.
# Split the string into a sequence of chunks, not by splitting the strings into chunks that contain L's and s's, but AT the character that appears the least. Because every chunk contains at least one L and at least one s, removing the character that appears the least will not make any difference to how the chunks are ordered in terms of size. If there are more L's than s's, then there should be exactly y chunks consisting of only L's, and if there are more s's than L's, then there should be exactly x chunks consisting of only s's. If there is exactly one more string than expected, this may be because the string was in a mode that split one of the chunks into two; in this case, combine the first and last chunks in the sequence back into one chunk to get the correct number of chunks.
# Count how many UNIQUE chunks there are. If there are more than two unique strings, then the scale is not MOS. If there are only two unique strings but their lengths differ by more than 1, then the scale is not MOS.
# Count how many UNIQUE chunks there are. If there are more than two unique strings, then the scale is not maximally even. If there are only two unique strings but their lengths differ by more than 1, then the scale is not maximally even.
# Produce a new scale consisting of L's and s's, based on the sequence of tokenized strings, as this will be the progenitor scale of the original; in the sequence, every instance of the larger string corresponds to an L in the progenitor scale, and every instance of the smaller string corresponds to an s in that scale. Call this algorithm recursively on that scale to determine whether that scale is also MOS. If that scale is MOS, then the original scale is MOS. Otherwise, the scale is not MOS.
# Produce a new scale consisting of L's and s's, based on the sequence of tokenized strings, as this will be the progenitor scale of the original; in the sequence, every instance of the larger string corresponds to an L in the progenitor scale, and every instance of the smaller string corresponds to an s in that scale. Call this algorithm recursively on that scale to determine whether that scale is also maximally even. If that scale is maximally even, then the original scale is maximally even. Otherwise, the scale is not maximally even.


=== Pseudocode ===
=== Pseudocode ===
This is the pseudocode for the chunking operation described above.
This is the pseudocode for the chunking operation described above.
  VeridyMOSScale(string scale : scale encodes an arbitrary scale of only L's and s's) returns TRUE or FALSE {
  VerifyMaximallyEvenScale(string scale : scale encodes an arbitrary scale of only L's and s's) returns TRUE or FALSE {
   
   
  integer x = 0;
  integer x = 0;
Line 97: Line 97:
  } else {
  } else {
  string subscale = set.beginning_of_set
  string subscale = set.beginning_of_set
  return VeridyMOSScale(subscale)
  return VerifyMaximallyEvenScale(subscale)
  }
  }
  }
  }
Line 153: Line 153:
  subscale += "L"
  subscale += "L"
   
   
  return VeridyMOSScale(subscale)
  return VerifyMaximallyEvenScale(subscale)
  }
  }
  }
  }
Line 177: Line 177:


=== Counterexamples ===
=== Counterexamples ===
LLLLsLs. This produces two unique chunks of LLLLs and Ls. However, the two chunks differ in size by two L's, and it is not MOS.
LLLLsLs. This produces two unique chunks of LLLLs and Ls. However, the two chunks differ in size by two L's, and it is not maximally even.


LLLLLss. This produces one chunk of LLLLLs. The lone s at the end can be considered a chunk consisting of zero L's and one s. Since the two chunks differ in size by 5 L's, this is not MOS.
LLLLLss. This produces one chunk of LLLLLs. The lone s at the end can be considered a chunk consisting of zero L's and one s. Since the two chunks differ in size by 5 L's, this is not maximally even.


LsssLsssL. The quantity of L's and s's are coprime, sharing a common factor of 3. However, dividing the scale into three equal-sized chunks shows that all three chunks are different (Lss, sLs, and ssL), so this is not MOS.
LsssLsssL. The quantity of L's and s's are coprime, sharing a common factor of 3. However, dividing the scale into three equal-sized chunks shows that all three chunks are different (Lss, sLs, and ssL), so this is not maximally even.


LLsLLLsLLLLs. This produces three unique chunks of LLs, LLLs, and LLLLs. This is not MOS.
LLsLLLsLLLLs. This produces three unique chunks of LLs, LLLs, and LLLLs. This is not maximally even.


== Finding the MOS pattern from xL ys ==
== Finding the MOS pattern from xL ys ==
Line 423: Line 423:


== Proofs ==
== Proofs ==
=== The equave splits into gcd(#L, #s) periods in aLbs<equave> ===
Suppose ''S'' is a MOS aLbs (a+b=n; WLOG equave = octave) and gcd(a, b) = d > 1.


Assume (n/d)-steps came in 2 sizes, pa+qb and ra+sb. Then at least one size, say pa+qb, must differ from (a/d)L + (b/d)s. WLOG p > a/d and pa+qb occurs on degree 0. Since equave = aL + bs, on a degree k(n/d) for some integer k > 0, there must be another (n/d)-step with fewer L's than a/d. This involves more than two changes from L to s. Scooting an (n/d)-step one step at a time from degree 0 to k(n/d) changes its size one step size substitution at a time, showing that intermediate (n/d)-steps also exist. This violates the MOS property, whence (n/d)-steps have only one size, which must be the period.
=== Preservation of the MOS property ===
(Assume that the mos has length n; the notation w(X, Y) for a word w(L, s) in L, s means w with step sizes X substituted for L and Y substituted for s.)
 
Suppose w(L, s) had three chunks L...s with r, r+1 and r+2 'L's. Then we have a length r+2 subword that's only 'L's, one that has one s at the end and one that has two 's's on either side, which means that the original scale was not MOS. Therefore the reduced word has two step sizes.
 
[Proof is incomplete]<!--
Without loss of generality assume r ≥ 1 (otherwise flip the roles of L and s). Let W'(λ, σ) be the reduced word with step sizes λ (corresponding to the chunk of L's of size r+1) and σ (corresponding the chunk of size r), and assume that W' is not a mos. Then for some k, W' must have k-steps of the following sizes:
# p₁ λ's and q₁ σ's, represented by subword W₁(λ, σ) in W'.
# p₂ λ's and q₂ σ's, represented by subword W₂(λ, σ) in W'. We can assume W₂ begins in λ; otherwise we can slink W₂ to the right until it begins in λ, which is guaranteed to never decrease the number of λ's.
Here, pᵢ + qᵢ = k and we assume p₂ - p₁ ≥ 2.
 
Let K = p₁(r + 1) + q₁r + k. Consider the following sizes for (K+1)-steps in w:
# w₁(L, s) = the word sW₁(L<sup>r+1</sup>s, L<sup>r</sup>s) [W₁ interpreted as a subword of the original mos], with (k + 1) s's. w₁ is K+1 letters long.
# w₂(L, s) = the first K+1 letters of W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) (which must be longer than w₁(L, s), since W₂ had more λ's than W₁)
# w₃(L, s) = the last K+1 letters of W₂(L<sup>r+1</sup>s, L<sup>r</sup>s)
Note that the latter two words have at most k s's, and that W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) has k chunks in total.
 
It suffices to consider the case where the intersection w₂ ∩ w₃ contains at least k-1 complete chunks, since otherwise we would contradict either the length of W₂(λ, σ) or the mos property of w (Todo: bring back the cases and diagrams to prove this rigorously). If the intersection had exactly k-1 chunks, this implies that one substring is a proper subset of the other, a contradiction. Thus the intersection has to have exactly k chunks, implying w₂ = w₃, and that W₂(L<sup>r+1</sup>s, L<sup>r</sup>s) is exactly K+1 letters long, only one more than w₁(L, s). This contradicts the fact that W₂(λ, σ) has at least two more λ's than W₁(λ, σ).-->


=== Preservation of generators ===
=== Preservation of generators ===
Line 435: Line 450:
=== Reflection of generators ===
=== Reflection of generators ===
Suppose there is a generator after chunking. Assume also that there are more L's than s's, and that the imperfect generator is larger than the perfect generator. This means that this interval, built on the chunk boundaries after expanding, will still be "a generator" on the chunk boundaries: it will be the same size on all but one of the chunk boundaries. Take one of the "perfect" (smaller) intervals. We showed previously that, before expansion, the step to its right was an L, just like its first step; therefore we can scoot it over for the entirety of the first chunk and keep it perfect. We now come to another chunk. If a "perfect" interval can be built on it then we can repeat. If the interval is imperfect, then we know that the step to its right is an s, which will make it smaller and thus perfect, and we can keep doing this for the remainder of the chunk. Therefore, the interval is a generator after expansion as well, since it is only imperfect in one position.
Suppose there is a generator after chunking. Assume also that there are more L's than s's, and that the imperfect generator is larger than the perfect generator. This means that this interval, built on the chunk boundaries after expanding, will still be "a generator" on the chunk boundaries: it will be the same size on all but one of the chunk boundaries. Take one of the "perfect" (smaller) intervals. We showed previously that, before expansion, the step to its right was an L, just like its first step; therefore we can scoot it over for the entirety of the first chunk and keep it perfect. We now come to another chunk. If a "perfect" interval can be built on it then we can repeat. If the interval is imperfect, then we know that the step to its right is an s, which will make it smaller and thus perfect, and we can keep doing this for the remainder of the chunk. Therefore, the interval is a generator after expansion as well, since it is only imperfect in one position.
=== Binary generated scales with #L coprime to #s within each period are MOS ===
By ''generatedness'', we mean that every interval in the scale is of the form ''jg'' + ''kp'' where ''g'' is a generator, ''p'' is the period, and ''j, k'' ∈ '''Z''', and that either ''g'' or ''&minus;g'' occurs on every note. We have shown that the chunking procedure yields a scale that is generated and binary and that has gcd(#L, #s) = 1 within each period. We need only show that any such scale is a MOS. We claim that any interval class not ''p''-equivalent to 0 has ''exactly'' 2 sizes.
Suppose that such a scale ''S'' (with ''n'' ≥ 2 notes) has ''a''-many L steps and ''b''-many s steps per period ''p'', and has generator ''g''. Since ''S'' is generated, the interval sizes modulo ''p'' that occur in ''S'' are:
{(&minus;''n'' + 1)''g'', ..., &minus;''g'', 0, ''g'', ..., (''n'' &minus; 1)''g''},
and all sizes {0, ''g'', ..., (''n'' &minus; 1)''g''} are distinct.
We thus have:
L = ''cg'' + ''dp''
s = ''eg'' + ''fp''
for appropriate integers ''c, d, e, f'', where |''c''| < ''n'' and |''e''| < ''n''.
Now we assume that ''g'' and ''p'' are linearly independent. By assumption ''a''L + ''b''s = (''ac'' + ''be'')''g'' + (''ad'' + ''bf'')''p'' = ''p''. Since ''a''L + ''b''s occurs on the "brightest" mode, from generatedness we have ''ac'' + ''be'' ∈ {0, ..., ''n'' &minus; 1}. Hence we must have ''ac'' + ''be'' = 0, and thus ''c'' = ±''b'' and ''e'' = ∓''a'', from the assumption that gcd(a, b) = 1.
In fact, {L, s} is another valid basis for the abelian group with basis {''p'', ''g''}, since by binarity we have ''p, g'' ∈ span(L, s). Assume ''c'' = ''b'' and ''e'' = &minus;''a''. [This corresponds to assuming that ''g'' is the "bright" generator.] Let χ = L &minus; s > 0; then χ is ''p''-equivalent to ''+ng''. Now by generatedness and binarity, any interval class that has at least two sizes must have sizes separated by ''ng'' (the separation corresponding to changing an L step to an s step). Since ''g'' and ''p'' are linearly independent, for each ''j'' ∈ {1, ..., ''n'' &minus; 1} there exists at most one ''k'' = ''k''(''j'') ∈ {1, ..., ''n'' &minus; 1}</sub> such that ''jg'' is ''p''-equivalent to one size of ''k''-step. Hence if the class of ''k''-steps has ''at least'' two sizes, the sizes must be ''j''(''k'')''g'' and (''j''(''k'') &minus; ''n'')''g''; any other size must leave the range &minus;(''n'' &minus; 1)''g'', ..., 0, ..., (''n'' &minus; 1)''g''. Thus the class of ''k''-steps has at most two sizes for 1 ≤ ''k'' ≤ (''n'' &minus; 1). Each non-''p''-equivalent class must have ''exactly'' two sizes, since the inverse of the ''k''-step that is equivalent to ''jg'' is an (''n'' &minus; ''k'')-step equivalent to ''&minus;jg'', which by linear independence must be distinct from an (''n'' &minus; ''k'')-step equivalent to a positive number of ''g'' generators. (Note that the latter (''n'' &minus; ''k'')-step does occur in the "brightest" mode of ''S'', i.e. the mode with the most ''g'' generators stacked ''up'' rather than ''down'' from the tonic.)
To establish MOSness in the case of non-linearly-independent ''p'' and ''g'', observe that every ''k''-step (which is a specific linear combination of L and s) in the scale with rational step ratio is a limit point of the same linear combination of L and s in versions of the binary scale with linearly independent ''p'' and ''g'', and thus there must be ''at most'' 2 sizes for each generic interval. Since χ, which separates the two sizes in the previous case, is ''p''-equivalent to ''ng'' and remains ''p''-inequivalent to 0 in the limit since L/s ≠ 1/1, each generic interval not ''p''-equivalent to 0 has ''exactly'' 2 sizes.
=== Reduction preserves the MOS property ===
Suppose w(L, s) had three chunks L...s with r, r+1 and r+2 'L's. Then we have a length r+2 subword that's only 'L's, one that has one s at the end and one that has two 's's on either side, which means that the original scale was not MOS. Therefore the reduced word has two step sizes. The number of chunks is b, and gcd(a%b, (b-a%b)) = gcd(a%b, b) =  gcd(a,b) by the Euclidean algorithm. Moreover, we have seen that the reduced word is generated. Thus the previous lemma shows that this reduced scale must be a MOS.


=== Uniqueness and existence of the generator===
=== Uniqueness and existence of the generator===
Line 465: Line 455:


It is clear that the MOS nL 1s has a unique generator, L (or its inversion). However, the previous proof showed that reduction reflects generators, and so by induction all MOS scales have a single generator.
It is clear that the MOS nL 1s has a unique generator, L (or its inversion). However, the previous proof showed that reduction reflects generators, and so by induction all MOS scales have a single generator.
=== Child MOSes exist ===
{{todo|expand|inline=1}}
Going from a MOS scale aL bs and applying rules L → Ls, s → s ''or'' L → L, s → Ls, we end up with the child scales aL (a+b)s or (a+b)L bs. The layout of these scales is such that the [[#Stepwise version|stepwise algorithm]] immediately says these two are MOS too: in both cases, first we either exactly de-apply the rules given here, and end up with the parent scale which was chosen to be a MOS, or we get to an L↔s reversed scale with b L’s and a s’s which should end up being MOS too, for some clear reason not stated here right now yet.


== See also ==
== See also ==
Retrieved from "https://en.xen.wiki/w/Recursive_structure_of_MOS_scales"