Interval variety: Difference between revisions

Line 12:

== Terminology ==

For abstract scale words, the standard academic counterpart to the xen term ''variety'' is the ''abelian complexity function of a [[word]]'': a function ρ<sup>ab</sup>: {{nowrap|'''N''' → '''N'''}} where ρ<sup>ab</sup>(''n'') is the number of distinct sizes (abelianizations, living in a free abelian group over the step sizes) that length-''n'' subwords can have in a word.

The '''maximum variety''' ('''MV''') of a scale is a way of quantifying how many different "flavors" of intervals there are in it. Scales with high maximum variety have many different intervals of similar size occuring at different places in the scale. Scales with low maximum variety may be easier for composers and listeners to understand, because there is more uniformity and consistence between different parts of the scale. In a low maximum variety scale, simply knowing how many scale steps an interval spans gives you a lot of information about the interval (by narrowing it down to a small set of choices).

Line 119:

In the following, two letters are to be considered the same if their numerical values are congruent modulo ''n''.

{{theorem|contents=For all ''n'' ≥ 1, the word '''0123'''...('''''n''-1''') is SV''n''.}}

{{theorem|contents=For all ''n'' ≥ 1, the word '''0123'''...({{nowrap|'''''n'' − 1'''}}) is SV''n''.}}

{{Proof|contents=All ''k''-letter subwords of '''0123'''...('''''n''-1''') is of the form ('''i''')('''i+1''')...('''i+k-1'''), and there are exactly ''n'' of them.}}

{{Proof|contents=All ''k''-letter subwords of '''0123'''...({{nowrap|'''''n'' − 1'''}}) is of the form ('''i''')({{nowrap|'''i + 1'''}})...({{nowrap|'''i + k − 1'''}}), and there are exactly ''n'' of them.}}

{{theorem|contents=For all ''n'' ≥ 1, the word '''0123'''...('''''n''-2''')('''''n''-1''')('''''n''-2''')...'''3210''' is SV''n''.}}

{{theorem|contents=For all ''n'' ≥ 1, the word '''0123'''...({{nowrap|'''''n'' − 2'''}})({{nowrap|'''''n'' − 1'''}})({{nowrap|'''''n'' − 2'''}})...'''3210''' is SV''n''.}}

{{Proof|contents=We prove this by dividing this word into four overlapping noncircular subwords which cover all cases.

Consider the subwords '''0123'''...('''''n''-2''')('''''n''-1''') and ('''''n''-1''')('''''n''-2''')...'''3210'''. If we treat these two words as noncircular, then there are ''n''-''k'' distinct ''k''-letter subwords.

Consider the subwords '''0123'''...({{nowrap|'''''n'' − 2'''}})({{nowrap|'''''n'' − 1'''}}) and ({{nowrap|'''''n'' − 1'''}})({{nowrap|'''''n'' − 2'''}})...'''3210'''. If we treat these two words as noncircular, then there are {{nowrap|''n'' − ''k''}} distinct ''k''-letter subwords.

Now consider the ''k''-letter noncircular subword ('''r-1''')('''r-2''')...'''210012'''...('''s-2''')('''s-1'''), where ''r'', ''s'' ≥ 1. Note that interchanging ''r'' and ''s'' yields equivalent subwords. If ''k'' is odd, there are (''k''-1)/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of ''r'' + ''s'' ≥ ''k''.

Now consider the ''k''-letter noncircular subword ({{nowrap|'''r − 1'''}})({{nowrap|'''r − 2'''}})...'''210012'''...({{nowrap|'''s − 2'''}})({{nowrap|'''s − 1'''}}), where {{nowrap|''r'', ''s'' &geqslant; 1}}. Note that interchanging ''r'' and ''s'' yields equivalent subwords. If ''k'' is odd, there are ({{nowrap|''k'' − 1}})/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of {{nowrap|''r'' + ''s'' &geqslant; ''k''}}.

A similar thing goes with ('''''n''-''r''-1''')...('''''n''-2''')('''''n''-1''')('''''n''-2''')..('''''n''-''s''-1'''). If ''k'' is odd, there are (''k''+1)/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of ''r'' + ''s'' - 1 ≥ ''k''.

A similar thing goes with ({{nowrap|'''''n'' − ''r'' − 1'''}})...({{nowrap|'''''n'' − 2'''}})({{nowrap|'''''n'' − 1'''}})({{nowrap|'''''n'' − 2'''}})..({{nowrap|'''''n'' − ''s'' − 1'''}}). If ''k'' is odd, there are ({{nowrap|''k'' + 1}})/2 distinct subwords of this kind; if ''k'' is even, there are {{nowrap|''k'' / 2}} subwords, each corresponding to a solution of {{nowrap|''r'' + ''s'' − 1 ≥ ''k''}}.

Thus there are

~~(''~~n'' - ''k~~'')~~ + ~~(''~~k''-1)/2 + ~~(''~~k''+1)/2 = ''n'' (''k'' odd)

<math>n - k + \frac{k - 1}{2} + \frac{k + 1}{2} = n \qquad \left(k\,\text{odd}\right)</math>

(''n'' - ''k'') + 2(''k~~''/~~2) = ''n'' (''k'' even)

<math>(n - k) + 2\left(\frac{k}{2}\right) = n \qquad \left(k\,\text{even}\right)</math>

distinct ''k''-letter subwords, so the word is SV''n''.}}

Line 155:

Conjecture: there are no SV4 scale patterns with more than 10 notes.

=== Maximum variety of balanced words ===

A [[balanced]] word or [[necklace]] in ''N'' letters has a maximum variety bound of <math> N \choose {\lceil N/2 \rceil}</math>.

A [[balanced]] word or [[necklace]] in ''N'' letters has a maximum variety bound of <math> N \choose {\left\lceil N/2 \right\rceil}</math>.

== Open questions ==

* Why are (abstractly) SV4 scale patterns seemingly so rare?

** Conjecture: There are only finitely many SV4/MV4 [[circular word]]s.

** Conjecture: For all ''n'' greater than a sufficiently large ''m'', the longest abstractly SV''n'' word is '''0123'''...('''''n''−2''')('''''n''−1''')('''''n''−2''')...'''3210''', with length 2''n'' - 1.

** Conjecture: For all ''n'' greater than a sufficiently large ''m'', the longest abstractly SV''n'' word is '''0123'''...({{nowrap|'''''n'' − 2'''}})({{nowrap|'''''n'' − 1'''}})({{nowrap|'''''n'' − 2'''}})...'''3210''', with length {{nowrap|2''n'' − 1}}.

** The following conjecture may be key to proving the ones above: For a sufficiently long [[arity|ternary]] noncircular word, there exists ''k'' > 1 such that the interval class of ''k''-steps has at least 3 sizes and the interval class of (''k'' − 1)-steps also has at least 3 sizes.

** The following conjecture may be key to proving the ones above: For a sufficiently long [[arity|ternary]] noncircular word, there exists {{nowrap|''k'' > 1}} such that the interval class of ''k''-steps has at least 3 sizes and the interval class of (''k'' − 1)-steps also has at least 3 sizes.

[[Category:Combinatorics on words]]

[[Category:Scale]]

@@ Line 12: / Line 12: @@
 == Terminology ==
-For abstract scale words, the standard academic counterpart to the xen term ''variety'' is the ''abelian complexity function of a [[word]]'': a function ρ<sup>ab</sup>: {{nowrap|'''N''' &rarr; '''N'''}} where ρ<sup>ab</sup>(''n'') is the number of distinct sizes (abelianizations, living in a free abelian group over the step sizes) that length-''n'' subwords can have in a word.
+For abstract scale words, the standard academic counterpart to the xen term ''variety'' is the ''abelian complexity function of a [[word]]'': a function &rho;<sup>ab</sup>: {{nowrap|'''N''' &rarr; '''N'''}} where &rho;<sup>ab</sup>(''n'') is the number of distinct sizes (abelianizations, living in a free abelian group over the step sizes) that length-''n'' subwords can have in a word.
 The '''maximum variety''' ('''MV''') of a scale is a way of quantifying how many different "flavors" of intervals there are in it. Scales with high maximum variety have many different intervals of similar size occuring at different places in the scale. Scales with low maximum variety may be easier for composers and listeners to understand, because there is more uniformity and consistence between different parts of the scale. In a low maximum variety scale, simply knowing how many scale steps an interval spans gives you a lot of information about the interval (by narrowing it down to a small set of choices).
@@ Line 119: / Line 119: @@
 In the following, two letters are to be considered the same if their numerical values are congruent modulo ''n''.
-{{theorem|contents=For all ''n'' ≥ 1, the word '''0123'''...('''''n''-1''') is SV''n''.}}
+{{theorem|contents=For all ''n'' ≥ 1, the word '''0123'''...({{nowrap|'''''n'' &minus; 1'''}}) is SV''n''.}}
-{{Proof|contents=All ''k''-letter subwords of '''0123'''...('''''n''-1''') is of the form ('''i''')('''i+1''')...('''i+k-1'''), and there are exactly ''n'' of them.}}
+{{Proof|contents=All ''k''-letter subwords of '''0123'''...({{nowrap|'''''n'' &minus; 1'''}}) is of the form ('''i''')({{nowrap|'''i + 1'''}})...({{nowrap|'''i + k &minus; 1'''}}), and there are exactly ''n'' of them.}}
-{{theorem|contents=For all ''n'' ≥ 1, the word '''0123'''...('''''n''-2''')('''''n''-1''')('''''n''-2''')...'''3210''' is SV''n''.}}
+{{theorem|contents=For all ''n'' ≥ 1, the word '''0123'''...({{nowrap|'''''n'' &minus; 2'''}})({{nowrap|'''''n'' &minus; 1'''}})({{nowrap|'''''n'' &minus; 2'''}})...'''3210''' is SV''n''.}}
 {{Proof|contents=We prove this by dividing this word into four overlapping noncircular subwords which cover all cases.
-Consider the subwords '''0123'''...('''''n''-2''')('''''n''-1''') and ('''''n''-1''')('''''n''-2''')...'''3210'''. If we treat these two words as noncircular, then there are ''n''-''k'' distinct ''k''-letter subwords.
+Consider the subwords '''0123'''...({{nowrap|'''''n'' &minus; 2'''}})({{nowrap|'''''n'' &minus; 1'''}}) and ({{nowrap|'''''n'' &minus; 1'''}})({{nowrap|'''''n'' &minus; 2'''}})...'''3210'''. If we treat these two words as noncircular, then there are {{nowrap|''n'' &minus; ''k''}} distinct ''k''-letter subwords.
-Now consider the ''k''-letter noncircular subword ('''r-1''')('''r-2''')...'''210012'''...('''s-2''')('''s-1'''), where ''r'', ''s'' ≥ 1. Note that interchanging ''r'' and ''s'' yields equivalent subwords. If ''k'' is odd, there are (''k''-1)/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of ''r'' + ''s'' ≥ ''k''.
+Now consider the ''k''-letter noncircular subword ({{nowrap|'''r &minus; 1'''}})({{nowrap|'''r &minus; 2'''}})...'''210012'''...({{nowrap|'''s &minus; 2'''}})({{nowrap|'''s &minus; 1'''}}), where {{nowrap|''r'', ''s'' &geqslant; 1}}. Note that interchanging ''r'' and ''s'' yields equivalent subwords. If ''k'' is odd, there are ({{nowrap|''k'' &minus; 1}})/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of {{nowrap|''r'' + ''s'' &geqslant; ''k''}}.
-A similar thing goes with ('''''n''-''r''-1''')...('''''n''-2''')('''''n''-1''')('''''n''-2''')..('''''n''-''s''-1'''). If ''k'' is odd, there are (''k''+1)/2 distinct subwords of this kind; if ''k'' is even, there are ''k''/2 subwords, each corresponding to a solution of ''r'' + ''s'' - 1 ≥ ''k''.
+A similar thing goes with ({{nowrap|'''''n'' &minus; ''r'' &minus; 1'''}})...({{nowrap|'''''n'' &minus; 2'''}})({{nowrap|'''''n'' &minus; 1'''}})({{nowrap|'''''n'' &minus; 2'''}})..({{nowrap|'''''n'' &minus; ''s'' &minus; 1'''}}). If ''k'' is odd, there are ({{nowrap|''k'' + 1}})/2 distinct subwords of this kind; if ''k'' is even, there are {{nowrap|''k'' / 2}} subwords, each corresponding to a solution of {{nowrap|''r'' + ''s'' &minus; 1 ≥ ''k''}}.
 Thus there are
-(''n'' - ''k'') + (''k''-1)/2 + (''k''+1)/2 = ''n'' (''k'' odd)
+<math>n - k + \frac{k - 1}{2} + \frac{k + 1}{2} = n \qquad \left(k\,\text{odd}\right)</math>
-(''n'' - ''k'') + 2(''k''/2) = ''n'' (''k'' even)
+<math>(n - k) + 2\left(\frac{k}{2}\right) = n \qquad \left(k\,\text{even}\right)</math>
 distinct ''k''-letter subwords, so the word is SV''n''.}}
@@ Line 155: / Line 155: @@
 Conjecture: there are no SV4 scale patterns with more than 10 notes.
 === Maximum variety of balanced words ===
-A [[balanced]] word or [[necklace]] in ''N'' letters has a maximum variety bound of <math> N \choose {\lceil N/2 \rceil}</math>.
+A [[balanced]] word or [[necklace]] in ''N'' letters has a maximum variety bound of <math> N \choose {\left\lceil N/2 \right\rceil}</math>.
 == Open questions ==
 * Why are (abstractly) SV4 scale patterns seemingly so rare?
 ** Conjecture: There are only finitely many SV4/MV4 [[circular word]]s.
-** Conjecture: For all ''n'' greater than a sufficiently large ''m'', the longest abstractly SV''n'' word is '''0123'''...('''''n''&minus;2''')('''''n''&minus;1''')('''''n''&minus;2''')...'''3210''', with length 2''n'' - 1.
+** Conjecture: For all ''n'' greater than a sufficiently large ''m'', the longest abstractly SV''n'' word is '''0123'''...({{nowrap|'''''n'' &minus; 2'''}})({{nowrap|'''''n'' &minus; 1'''}})({{nowrap|'''''n'' &minus; 2'''}})...'''3210''', with length {{nowrap|2''n'' &minus; 1}}.
-** The following conjecture may be key to proving the ones above: For a sufficiently long [[arity|ternary]] noncircular word, there exists ''k'' > 1 such that the interval class of ''k''-steps has at least 3 sizes and the interval class of (''k'' &minus; 1)-steps also has at least 3 sizes.
+** The following conjecture may be key to proving the ones above: For a sufficiently long [[arity|ternary]] noncircular word, there exists {{nowrap|''k'' > 1}} such that the interval class of ''k''-steps has at least 3 sizes and the interval class of (''k'' &minus; 1)-steps also has at least 3 sizes.
 [[Category:Combinatorics on words]]
 [[Category:Scale]]