Interval variety: Difference between revisions

Line 11:

Note: A standard academic counterpart to the xen term ''variety'' is the ''abelian complexity function of a [[word]]'': a function ρ<sup>ab</sup> : '''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.

== Facts ==

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

Theorem: for all ''n'' ≥ 1, the word '''0123'''...('''''n''-1''') is SV''n''.

Proof: 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.

Theorem: for all ''n'' ≥ 1, the word '''0123'''...('''''n''-2''')('''''n''-1''')('''''n''-2''')...'''3210''' is SV''n''.

Proof: 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 there two words as noncircular, then there are ''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, which is a subword that strictly intersects the middle of the original word. 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''.

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''.

Thus there are

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

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

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

=== Abstractly SV4 scale patterns ===

Abstractly SV4 scale patterns (patterns that are SV4 for any choice of distinct cent values for the four steps):

@@ Line 11: / Line 11: @@
 Note: A standard academic counterpart to the xen term ''variety'' is the ''abelian complexity function of a [[word]]'': a function ρ<sup>ab</sup> : '''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.
 == Facts ==
+In the following, two letters are to be considered the same if their numerical values are congruent modulo ''n''.
 Theorem: for all ''n'' ≥ 1, the word '''0123'''...('''''n''-1''') is SV''n''.
+Proof: 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.
 Theorem: for all ''n'' ≥ 1, the word '''0123'''...('''''n''-2''')('''''n''-1''')('''''n''-2''')...'''3210''' is SV''n''.
-<!-- prove these -->
+Proof: 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 there two words as noncircular, then there are ''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, which is a subword that strictly intersects the middle of the original word. 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''.
+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''.
+Thus there are
+(''n'' - ''k'') + (''k''-1)/2 + (''k''+1)/2 = ''n'' (''k'' odd)
+(''n'' - ''k'') + 2(''k''/2) = ''n'' (''k'' even)
+distinct ''k''-letter subwords, so the word is SV''n''.
 === Abstractly SV4 scale patterns ===
 Abstractly SV4 scale patterns (patterns that are SV4 for any choice of distinct cent values for the four steps):