Recursive structure of MOS scales: Difference between revisions

Line 423:

== Proofs ==

~~=== 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₁(Lr+1s, Lrs) [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₂(Lr+1s, Lrs) (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₂(Lr+1s, Lrs)~~

~~Note that the latter two words have at most k s's, and that W₂(Lr+1s, Lrs) 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₂(Lr+1s, Lrs) 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 ===

Assume there are more L's and s's, and that there is more than one s, and thus more than one chunk. Assume there is a generator. Assume the imperfect generator is bigger than the perfect generator. (If this isn't true, just use the inverted generator.) Because there are at least two chunk boundaries, and only one imperfect generator, there must be a chunk boundary with a perfect generator on top (the chunk boundary is on the left of the generator, e.g. <code>...|Ls|LLs|Ls...</code>). Because there's a chunk boundary to the left, there's an s just to the left of the left endpoint of the generator. If the rightmost step of this generator were an L, scooting the generator one step to the left would make it smaller, which contradicts the assumption that the imperfect generator is larger than perfect. Thus, the rightmost step of this generator is an s. That means the right endpoint of this generator falls on a chunk boundary. We already know the left endpoint also falls on a chunk boundary, so this perfect generator is still present as an interval in the reduced MOS.

Line 456:

Line 436:

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~~ ===

=== Reduced words from chunking are binary ===

{~~{todo~~|~~expand~~|~~inline~~=1}}

It now remains to show that reduction and expansion preserve 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.

=== Binary generated scales are MOS ===

By ''generatedness'', we mean that every interval in the scale is of the form ''jg'' + ''kp'' where ''g'' is the generator, ''p'' is the period, and ''j, k'' ∈ '''Z'''. We have shown that the result of chunking and reduction is generated and binary and the result of expanding from a reduced word is generated and binary. We need only show that binary generated scales are MOS (i.e. satisfy Myhill's property).

First suppose that ''g'' and ''p'' are linearly independent, so the step ratio of ''S'' is irrational.

Suppose that such a scale ''S'' (with ''n'' ≥ 2 notes) has ''a''-many L steps and ''b''-many s steps and has generator ''g'' and period ''p''. Since ''S'' is generated, the interval sizes modulo ''p'' that occur in ''S'' are:

{(−''n'' + 1)''g'', ..., −''g'', 0, ''g'', ..., (''n'' − 1)''g''}.

We thus have:

L = ''cg'' + ''dp''

s = ''eg'' + ''fp''

for appropriate integers ''c, d, e, f'', |''c''| < ''n'', and |''e''| < ''n''. We must have that ''c'' = ±''b'' and ''e'' = ∓''a'', as by assumption ''a''L + ''b''s = (''ac'' + ''be'')''g'' + (''ad'' + ''bf'')''p'' = ''p''. In fact, [L, s] is another valid basis for the group generated by ''p'' and ''g'', since by binarity we have ''p, g'' ∈ span(''L, s'').

Assume ''c'' = ''b'' and ''e'' = -''a''. Let χ = L − s > 0; then χ is ''p''-equivalent to ''+ng''. Now by generatedness, binarity, and linear independence of ''p'' and ''g'', the class of ''k''-steps must have two sizes separated by ''ng'', and changing the k-steps outside these two sizes leaves the range −(''n'' − 1)''g'', ..., 0, ..., (''n'' − 1)''g''. Thus the class of ''k''-steps has two sizes for 1 ≤ ''k'' ≤ (''n'' − 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~~.

To show binarity for rational step ratios, note 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 irrational step ratios, and thus there must be ''at most'' 2 sizes for each generic interval. Since χ, which separates the two sizes, is ''p''-equivalent to ''ng'', which remains ''p''-inequivalent to 0 since L/s ≠ 1/1, each generic interval has ''exactly'' 2 sizes.

== See also ==

@@ Line 423: / Line 423: @@
 == Proofs ==
-=== 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 ===
 Assume there are more L's and s's, and that there is more than one s, and thus more than one chunk. Assume there is a generator. Assume the imperfect generator is bigger than the perfect generator. (If this isn't true, just use the inverted generator.) Because there are at least two chunk boundaries, and only one imperfect generator, there must be a chunk boundary with a perfect generator on top (the chunk boundary is on the left of the generator, e.g. <code>...|Ls|LLs|Ls...</code>). Because there's a chunk boundary to the left, there's an s just to the left of the left endpoint of the generator. If the rightmost step of this generator were an L, scooting the generator one step to the left would make it smaller, which contradicts the assumption that the imperfect generator is larger than perfect. Thus, the rightmost step of this generator is an s. That means the right endpoint of this generator falls on a chunk boundary. We already know the left endpoint also falls on a chunk boundary, so this perfect generator is still present as an interval in the reduced MOS.
@@ Line 456: / Line 436: @@
 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 ===
+=== Reduced words from chunking are binary ===
-{{todo|expand|inline=1}}
+It now remains to show that reduction and expansion preserve 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.
+=== Binary generated scales are MOS ===
+By ''generatedness'', we mean that every interval in the scale is of the form ''jg'' + ''kp'' where ''g'' is the generator, ''p'' is the period, and ''j, k'' ∈ '''Z'''. We have shown that the result of chunking and reduction is generated and binary and the result of expanding from a reduced word is generated and binary. We need only show that binary generated scales are MOS (i.e. satisfy Myhill's property).
+First suppose that ''g'' and ''p'' are linearly independent, so the step ratio of ''S'' is irrational.
+Suppose that such a scale ''S'' (with ''n'' ≥ 2 notes) has ''a''-many L steps and ''b''-many s steps and has generator ''g'' and period ''p''. 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''}.
+We thus have:
+L = ''cg'' + ''dp''
+s = ''eg'' + ''fp''
+for appropriate integers ''c, d, e, f'', |''c''| < ''n'', and |''e''| < ''n''. We must have that ''c'' = ±''b'' and ''e'' = ∓''a'', as by assumption ''a''L + ''b''s = (''ac'' + ''be'')''g'' + (''ad'' + ''bf'')''p'' = ''p''. In fact, [L, s] is another valid basis for the group generated by ''p'' and ''g'', since by binarity we have ''p, g'' ∈ span(''L, s'').
+Assume ''c'' = ''b'' and ''e'' = -''a''. Let χ = L &minus; s > 0; then χ is ''p''-equivalent to ''+ng''. Now by generatedness, binarity, and linear independence of ''p'' and ''g'', the class of ''k''-steps must have two sizes separated by ''ng'', and changing the k-steps outside these two sizes leaves the range &minus;(''n'' &minus; 1)''g'', ..., 0, ..., (''n'' &minus; 1)''g''. Thus the class of ''k''-steps has two sizes for 1 ≤ ''k'' ≤ (''n'' &minus; 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.
+To show binarity for rational step ratios, note 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 irrational step ratios, and thus there must be ''at most'' 2 sizes for each generic interval. Since χ, which separates the two sizes, is ''p''-equivalent to ''ng'', which remains ''p''-inequivalent to 0 since L/s ≠ 1/1, each generic interval has ''exactly'' 2 sizes.
 == See also ==