Ternary parallelogram scales are MOS substitution: Difference between revisions

Inthar (talk | contribs)
Inthar (talk | contribs)
 
(65 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{expert}}
This article proves the following theorem:
This article proves the following theorem:


''Ternary parallelogram scale words are [[MOS substitution]] scale words, where the period count of the template MOS is the number of rows of the parallelogram parallel to the unique step size parallel to a side of the parallelogram.''
''[[Ternary]] parallelogram scale [[word]]s are [[MOS substitution]] scale words, where the period count of the template MOS is the number of rows of the parallelogram parallel to the unique step size parallel to a side of the parallelogram.''
== Definitions ==
== Definitions ==
=== Pitch-class group ===
=== Pitch-class group ===
The ''pitch-class group'' of a scale word ''w'' in letters {{nowrap|'''x'''<sub>1</sub>, ..., '''x'''<sub>''r''</sub>}} with [[step signature]] {{nowrap|'''e''' ∈ ℤ<sup>''r''</sup>{{angbr|'''x'''<sub>1</sub>, ..., '''x'''<sub>''r''</sub>}}}} is the abelian group {{nowrap|C(''w'') :{{=}} ℤ<sup>''r''</sup>{{angbr|'''x'''<sub>1</sub>, ..., '''x'''<sub>''r''</sub>}}/{{angbr|'''e'''}}.}} The pitch-class group is associated with a canonical map π that sends every step vector to its pitch class.
The ''pitch-class group'' of a scale word ''w'' in letters {{nowrap|'''x'''<sub>1</sub>, ..., '''x'''<sub>''r''</sub>}} with [[step signature]] {{nowrap|'''e''' ∈ ℤ<sup>''r''</sup>{{angbr|'''x'''<sub>1</sub>, ..., '''x'''<sub>''r''</sub>}}}} is the abelian group {{nowrap|C(''w'') :{{=}} ℤ<sup>''r''</sup>{{angbr|'''x'''<sub>1</sub>, ..., '''x'''<sub>''r''</sub>}}/{{angbr|'''e'''}}.}} The pitch-class group is associated with a canonical map π that sends every step vector to its pitch class.
Below we take it as known that the gcd of the coordinates ''v''<sub>''i''</sub> of '''v''' ∈ ℤ<sup>''r''</sup> is 1 iff the quotient group ℤ<sup>''r''</sup>/{{angbr|'''v'''}} is torsion-free; this can be proven using Bézout's identity.


=== Parallelogram scale ===
=== Parallelogram scale ===
A scale word ''w'' is a ''parallelogram scale word'' if C(''w'') is torsion-free (equiv. a free abelian group) and there exists integers {{nowrap|''m'', ''n'' > 1}} and linearly independent elements '''v''' and '''w''' in C(''w'') such that the π-image of  
A scale word ''w'' is a ''parallelogram scale word'' if C(''w'') is torsion-free (equiv. a free abelian group) and there exist integers {{nowrap|''m'', ''n'' > 1}} and linearly independent elements '''v''' and '''w''' in C(''w'') such that the π-image of  


<math>\mathcal{I}_w :=  
<math>\mathcal{I}_w :=  
Line 17: Line 20:


=== MOS substitution scale ===
=== MOS substitution scale ===
See [[MOS substitution]].
A ternary scale word ''w''('''x'''<sub>1</sub>, '''x'''<sub>2</sub>, '''x'''<sub>3</sub>) is a ''MOS substitution'' scale word if there exists a permutation <math>\pi \in S_3</math> such that the following holds:
* identifying '''x'''<sub>π(1)</sub> and '''x'''<sub>π(2)</sub> results in a [[MOS]] scale word (called the ''template MOS'') and
* deleting all instances of '''x'''<sub>π(3)</sub> (called the ''slot letter'') results in a MOS scale word (called the ''filling MOS'').
 
== Proof ==
== Proof ==
=== Step 1: Get a surjective homomorphism <math>\mathbb{Z}^2 \to \mathbb{Z}/mn\mathbb{Z}</math> ===
=== Step 1: Get a surjective homomorphism <math>\varphi:\mathbb{Z}^2 \to \mathbb{Z}/mn\mathbb{Z}</math> ===
The π-image of any ''k''-step interval (abelianized slice) {{nowrap|ab(''w''[''i'' : ''i'' + ''k''])}} is identical to that of {{nowrap|ab(''w''[''i'' : ''i'' + ''k'' + ''mn'']).}} Hence there is a well-defined map from the pitch classes of intervals of ''w'' to {{nowrap|ℤ/''mn''ℤ.}} Traversing ''w'' step by step gives a traversal of {{nowrap|[0 : ''m''] × [0 : ''n'']}} where we label each grid point with the index of the current note in ''w''. We also recall that the pitch-class vector '''v''' has a representative that is a ''k''<sub>'''v'''</sub>-step interval in ''w'', {{nowrap|0 < ''k''<sub>'''v'''</sub> < ''mn'',}} and similarly for '''w'''.  
The π-image of any ''k''-step interval (abelianized slice) {{nowrap|ab(''w''[''i'' : ''i'' + ''k''])}} is identical to that of {{nowrap|ab(''w''[''i'' : ''i'' + ''k'' + ''mn'']).}} Hence there is a well-defined map from the pitch classes of intervals of ''w'' to {{nowrap|ℤ/''mn''ℤ.}} Because ''w'' is a parallelogram scale, traversing ''w'' step by step gives a traversal of {{nowrap|[0 : ''m''] × [0 : ''n'']}} where we label each grid point with the index of the current note in ''w''. We also recall that the pitch-class vector '''v''' has a representative that is a ''k''<sub>'''v'''</sub>-step interval in ''w'', {{nowrap|0 < ''k''<sub>'''v'''</sub> < ''mn'',}} and similarly for '''w'''.  


We thus wish to constrain ways of labeling {{nowrap|[0 : ''m''] × [0 : ''n'']}} with {{nowrap|ℤ/''mn''ℤ}} elements such that
We thus wish to constrain ways of labeling {{nowrap|[0 : ''m''] × [0 : ''n'']}} with {{nowrap|ℤ/''mn''ℤ}} elements such that
Line 36: Line 42:
as φ is a homomorphism. Hence corresponding elements of any two ''m'' × ''n'' windows get the same {{nowrap|ℤ/''mn''ℤ}} labeling under φ modulo a shift.
as φ is a homomorphism. Hence corresponding elements of any two ''m'' × ''n'' windows get the same {{nowrap|ℤ/''mn''ℤ}} labeling under φ modulo a shift.


=== Step 3: By ternarity, exactly one of the 1-step vectors is parallel to a coordinate axis ===
=== Step 3: By ternarity, one of the 1-step vectors is parallel to a coordinate axis ===
Consider the following four "quadrants":
Consider the following four "quadrants":
# ''Q''<sub>1</sub> = [0 : ''m''] × [0 : ''n'']
# ''Q''<sub>1</sub> = [0 : ''m''] × [0 : ''n'']
Line 42: Line 48:
# ''Q''<sub>3</sub> = [-''m'' + 1 : 1] × [-''n'' + 1 : 1]
# ''Q''<sub>3</sub> = [-''m'' + 1 : 1] × [-''n'' + 1 : 1]
# ''Q''<sub>4</sub> = [0 : ''m''] × [0 : ''n'']
# ''Q''<sub>4</sub> = [0 : ''m''] × [0 : ''n'']
By the previous step, φ restricted to any ''m'' × ''n'' window in ℤ<sup>2</sup> is surjective, hence all of the four windows ''Q''<sub>1</sub>, ..., ''Q''<sub>4</sub> have 1 somewhere in them. Call these positions '''u'''<sub>1</sub>, ..., '''u'''<sub>4</sub> (note that none of them are the zero vector). Since {{Nowrap|φ((0, 0)) {{=}} 0}} by another application of the previous step we have '''u'''<sub>1</sub>, ..., '''u'''<sub>4</sub> as the images of 1-step vectors of ''w''. Since ''w'' is ternary, exactly two of these vectors will be pairwise equal, say '''u'''<sub>''k''</sub> = '''u'''<sub>''l''</sub>. These four "quadrants" intersect in <math>[-m + 1 : m] \times \{0\} \cup \{0\} \times [-n + 1 : n],</math> entailing that '''u'''<sub>''k''</sub> = '''u'''<sub>''l''</sub> is on a coordinate axis (either the '''v'''-coordinate is 0 or the '''w'''-coordinate is 0 but not both).
By the previous step, φ restricted to any ''m'' × ''n'' window in ℤ<sup>2</sup> is surjective, hence all of the four windows ''Q''<sub>1</sub>, ..., ''Q''<sub>4</sub> have 1 somewhere in them. Call these positions '''u'''<sub>1</sub>, ..., '''u'''<sub>4</sub> (note that none of them are the zero vector). Since {{Nowrap|φ((0, 0)) {{=}} 0,}} by another application of the previous step we have '''u'''<sub>1</sub>, ..., '''u'''<sub>4</sub> as the images of 1-step vectors of ''w''. Since ''w'' is ternary, exactly two of these vectors will be pairwise equal, say '''u'''<sub>''k''</sub> = '''u'''<sub>''l''</sub>. These four "quadrants" intersect in <math>[-m + 1 : m] \times \{0\} \cup \{0\} \times [-n + 1 : n],</math> entailing that '''u'''<sub>''k''</sub> = '''u'''<sub>''l''</sub> is on a coordinate axis (either the '''v'''-coordinate is 0 or the '''w'''-coordinate is 0 but not both).
 
=== Lemma: If ''m'' > 1, ''n'' > 2, and ''a'' has order > ''n'' in {{nowrap|ℤ/''mn''ℤ}}, then {{nowrap|{0, ''a'', 2''a'', ..., (''n'' - 1)''a''}}} meets some window of &le; 2''m'' - 1 adjacent elements at least twice ===
Apply the pigeonhole principle: we have
 
<math>
\begin{align*}
\bigg\lceil \frac{mn}{2m-1} \bigg\rceil
&=\bigg\lceil \frac{n}{2-1/m} \bigg\rceil
\\ &\le \bigg\lceil \frac{2n}{3} \bigg\rceil < n.
\end{align*}</math>
 
The bin where two multiples of ''a'' coincide must have two distinct multiples of ''a'', because the order of ''a'' is > ''n''.


=== Step 4: The axial step is a MOS substitution slot letter ===
=== Step 4: The axial step is a MOS substitution slot letter ===
Line 65: Line 59:
Under the above assumption, since {{nowrap|φ(''t'''''v''') {{=}} 1}} we have that {{nowrap|φ('''v''') {{=}} ''k''<sub>'''v'''</sub>}} is a cyclic generator of the group {{nowrap|ℤ/''mn''ℤ,}} such that {{nowrap|''tk''<sub>'''v'''</sub> {{=}} 1 mod ''mn''.}} Multiplication by ''t'' is a group automorphism ψ of {{nowrap|ℤ/''mn''ℤ}} such that ψ(''k''<sub>'''v'''</sub>) = 1, so the first row {{nowrap|[0 : ''m''] × {0}}} is mapped as {{nowrap|ψφ((''i'', 0)) {{=}} ''i''}}; so the image of the first row under ψφ is {{nowrap|{0, ..., ''m'' - 1}.}}
Under the above assumption, since {{nowrap|φ(''t'''''v''') {{=}} 1}} we have that {{nowrap|φ('''v''') {{=}} ''k''<sub>'''v'''</sub>}} is a cyclic generator of the group {{nowrap|ℤ/''mn''ℤ,}} such that {{nowrap|''tk''<sub>'''v'''</sub> {{=}} 1 mod ''mn''.}} Multiplication by ''t'' is a group automorphism ψ of {{nowrap|ℤ/''mn''ℤ}} such that ψ(''k''<sub>'''v'''</sub>) = 1, so the first row {{nowrap|[0 : ''m''] × {0}}} is mapped as {{nowrap|ψφ((''i'', 0)) {{=}} ''i''}}; so the image of the first row under ψφ is {{nowrap|{0, ..., ''m'' - 1}.}}


Claim: ''k''<sub>'''w'''</sub> has order ''n'' in {{nowrap|ℤ/''mn''ℤ.}}
Claim: ψ(''k''<sub>'''w'''</sub>) (thus ''k''<sub>'''w'''</sub> as well) has order ''n'' in {{nowrap|ℤ/''mn''ℤ.}}


Proof: The order cannot be less than ''n'', lest we have {{nowrap|φ((0, ''uk''<sub>'''w'''</sub>)) {{=}} 0}} for some {{nowrap|0 < ''u'' < ''n'',}} contradicting injectivity of φ within a fundamental domain (following from Step 2).
Proof: The order cannot be less than ''n'', lest we have {{nowrap|φ((0, ''uk''<sub>'''w'''</sub>)) {{=}} 0}} for some {{nowrap|0 < ''u'' < ''n'',}} contradicting injectivity of φ within a fundamental domain (following from Step 2). If the order is ''N'' > ''n'', we have two cases.
 
* If ''n'' = 2, then by disjointness the image of the (0, 1) translation of [0 : ''m''] must be [''m'' : 2''m''], forcing ψ(''k''<sub>'''w'''</sub>) = ''m'' which is of order 2.
If the order is ''N'' > ''n'', we have two cases. If ''n'' = 2, then clearly the image of the (0, 1) translation of [0 : ''m''] must be [''m'' : 2''m''], forcing ''k''<sub>'''w'''</sub> = ''m'' which is of order 2. If ''m'' > 3, then by the lemma, {{nowrap|[0 : ''m''], [0 : ''m''] + ''a'', ..., [0 : ''m''] + (''n'' - 1)''a''}}, where ''a'' = ψ(''k''<sub>'''w'''</sub>), are not disjoint, contradicting injectivity.
* If ''n'' &ge; 3, assume by way of contradiction that {{nowrap|[0 : ''m''], [0 : ''m''] + ''a'', ..., [0 : ''m''] + (''n'' - 1)''a''}}, where ''a'' = ψ(''k''<sub>'''w'''</sub>), are disjoint. Then {{nowrap|[0 : ''m''], [0 : ''m''] + ''a'', ..., [0 : ''m''] + (''n'' - 2)''a''}} are disjoint. We ask: where do we place {{nowrap|[0 : ''m''] + (''n'' - 1)''a''?}}
** The number of remaining slots on all of {{nowrap|ℤ/''mn''ℤ}} is ''m''.
** There is no contiguous region of ''m'' unoccupied slots. If there were, then the (''n'' - 1) windows that have already been placed must have no gap between them. This implies that ''a'' generates {{angbr|''m''}} and has order ''n''. Hence there is no way to place {{nowrap|[0 : ''m''] + (''n'' - 1)''a''}} without it overlapping with one of the other windows.


The claim establishes that
The claim establishes that
# the two other 1-step vectors are not found on the axis orthogonal to the first vector, as that would imply order ''mn'', nor on the axis opposite to the first
# the two other 1-step vectors are not found on the axis orthogonal to the first vector, as that would imply order ''mn'' for ''k''<sub>'''w'''</sub>, nor on {{nowrap|[-''m'' + 1 : 0] × {0}}} as that contradicts ''k''<sub>'''v'''</sub> having order ''mn''
# φ is minimally periodic under translation by ''n'''''w'''. Hence the two non-axial 1's on the grid from the 0 at the origin are translated by ''n'''''w'''.
# φ is minimally periodic under translation by ''n'''''w'''. Hence the two non-axial 1's on the grid from the 0 at the origin are translated by ''n'''''w'''.
# Since ''m'' is of order ''n'', ''m'' must be found on the '''w'''-axis as well.
# Since ''m'' is of order ''n'', and the cyclic group {{nowrap|ℤ/''mn''ℤ}} has at most one subgroup of any given order, ''m'' must be found on the '''w'''-axis as well.


==== Template word is MOS ====
==== Template word is MOS ====
Since the two non-axial steps differ by ''n'''''w''', to identify the two we wrap ℤ<sup>2</sup> with the vector ''n'''''w''', identifying lattice points separated by ''n'''''w'''. This makes the space ℤ × ℤ/''n''ℤ. Now the image of <math>\pi(\mathcal{I}_w)</math> under this wrap is of the form [0 : ''m''] × ℤ/''n''ℤ. Note that ''m'' (its order being ''n'') is a generator of the ℤ/''n''ℤ factor, establishing (by minimality) that the period of the template word is ''m''. Now do another wrap, identifying ''m'' with 0, and we're left with [0 : ''m''] in ℤ. We're now in period-equivalent pitch-class space with one generator chain. Since the template word is binary we have a MOS with period ''m'' and period count ''n'', which is "the number of rows of the parallelogram parallel to the unique step size parallel to a side of the parallelogram."
Since the two non-axial steps differ by ''n'''''w''', to identify the two we wrap ℤ<sup>2</sup> with the vector ''n'''''w''', identifying lattice points separated by ''n'''''w'''. This makes the space ℤ × ℤ/''n''ℤ. Now the image of <math>\pi(\mathcal{I}_w)</math> under this wrap is of the form [0 : ''m''] × ℤ/''n''ℤ. Note that ''m'' (its order being ''n'') corresponds to a generator of the ℤ/''n''ℤ factor, establishing (by minimality) that the period of the template word is ''m''. Now do another wrap, identifying ''m'' with 0, and we're left with [0 : ''m''] in ℤ. We're now in period-equivalent pitch-class space with one generator chain. Since the template word is binary we have a MOS with period ''m'' and period count ''n'', which is "the number of rows of the parallelogram parallel to the unique step size parallel to a side of the parallelogram."


==== Filling word is MOS ====
==== Filling word is MOS ====
Delete all instances of the axial step '''u'''<sub>'''x'''</sub> and consider what the two remaining step sizes do to the '''w'''-coordinate.
Delete all instances of the axial step '''x''' and consider what the two remaining step sizes do to the '''w'''-coordinate.
 
Without loss of generality assume that {{nowrap|'''u'''<sub>'''y'''</sub> {{=}} (''b'', ''c''), ''c'' > 0,}} and {{nowrap|'''u'''<sub>'''z'''</sub> {{=}} (''b'', ''c'' - ''n'').}} As the '''v'''-coordinates of both vectors are equal, we only need to look at the '''w'''-coordinate. Since the '''w'''-coordinate of a point must stay within {{nowrap|[0 : ''n''],}} at any point it must follow the rule: "If the current '''w'''-coordinate + c &ge; ''n'', then move by ''c'' - ''n'' units (using the letter '''z'''). Otherwise, move by ''c'' units (using the letter '''y''')."


Without loss of generality assume that '''u'''<sub>'''y'''</sub> = (''b'', ''c''), ''c'' > 0, and '''u'''<sub>'''z'''</sub> = (''b'', ''c'' - ''n''). As the '''v'''-coordinates of both vectors are equal, we only need to look at the '''w'''-coordinate. Since the '''w'''-coordinate of a point must stay within [0 : ''n''], at any point it must follow the rule: "If the current '''w'''-coordinate + c &ge; ''n'', then move by ''c'' - ''n'' units (i.e. southward). Otherwise, move by ''c'' units (northward)."
This pattern of movements is in fact the same as the one produced by taking the circular word {{nowrap|''v'' {{=}} "1 1 1 ... 1 (1 - ''n'')"}} ((''n'' - 1)-many 1's) and stacking sums <math>\sum_{i=0}^{c-1} v[i_0+i]</math> of ''c''-step subwords. As the resulting word has only one bad position per period, the filling word can easily be seen to be MOS by stacking ''kc''-step subwords of ''v'' for {{nowrap|2 &le; ''k'' &le; length - 1.}} {{Qed}}


This pattern of movements is in fact the same as the one produced by taking the circular word {{nowrap|"1 1 1 ... 1 (1 - ''n'')"}} and stacking (abelianized) ''c''-step subwords. As there is only one bad position per period, the filling word can easily be seen to be MOS by stacking ''kc''-step subwords of the latter word for {{nowrap|2 &le; ''k'' &le; length - 1.}} {{Qed}}
== Open problems ==
# Conjecture: Ternary scales that are parallelogram substrings with full row length ''m'', full column length ''n'', and cardinality {{nowrap|''mn'' - 1}} are MOS substitution.
# Conjecture: Ternary scales that are parallelogram substrings with full row length ''m'', full column length ''n'', and cardinality {{nowrap|''mn'' - 2}} are MOS substitution.
# Prove a converse to this theorem.
#* <s>If the template MOS of a MOS substitution scale has m > 1 periods and the step signature's gcd = 1 => m × n parallelogram scale.</s> This is false as stated, since no 5L(3m7s) scale is a parallelogram scale.
#* Conjecture: If the template MOS of a MOS substitution scale has m > 1 periods, the step signature's gcd = 1, and the filling MOS is a multiMOS, then the scale is a parallelogram scale. (But the filling MOS need not be a multiMOS for a parallelogram scale: LLmLLsLLmLLsLLs is of type 10L(2m3s))
#* Conjecture: If a MOS substitution scale's template MOS is a multiMOS, and its step signature's gcd = 1, then its generator structure is a (possibly) *shifted* full parallelogram, i.e. either a full parallelogram or the first and last rows' lengths add up to the full row length.
[[Category:Math]]
[[Category:Pages with proofs]]
[[Category:Pages with proofs]]
[[Category:Combinatorics on words]]
[[Category:Pages with open problems]]