Ternary scale theorems: Difference between revisions

Line 296:

==== Proof ====

For 7.1.1: ~~It suffices~~ to show that (a) ternary balanced words are pairwise-MOS ~~and that~~ (b) ~~non~~-~~PWF~~ pairwise-MOS ~~scales are even-regular~~.

For 7.1.1: We showed previously that the Fraenkel, odd-regular, and even-regular circular words are balanced. Thus it remains to show that (a) ternary balanced words are pairwise-MOS (b) if ''a'' > ''b'' > ''c'', then ''s'' is equivalent to the Fraenkel word (c) assuming ''a'' != ''b'' = ''c'' any ''s'' that is not odd-regular or even-regular is not pairwise-MOS, thus is not balanced.

(a) Let ''s'' be a ternary balanced word; then for any given letter '''y''' the number of '''y'''s in a subword of any given length ''L'' varies by at most 1. Thus the same is true when we count all non-'''y''' letters in any subword of length ''L''; thus when we equate '''x''' and '''z''', the count of the resulting letter in any subword of length ''L'' differs by 1. Being a binary balanced word is one characterization of the MOS property.

(b) ~~Assume that the projection ''p'''''YZ'''~~(~~''s''~~) ~~identifying~~ ''~~'Y''' and '''Z'~~'' of ~~a primitive PMOS scale~~ ''s'' ~~with signature~~ ''ar'''''X''' ''b'''''Y''' ''~~c'''''Z''' is an ''r''-period MOS, {{nowrap|''r'' > 1}}, with step signature ''ar'''''X''' ''dr'''~~''W'''. ~~We claim that neither~~ ''b'' ~~nor~~ ''c'' ~~is divisible by ''r~~''. ~~Since ''p'''''XY'''~~(''s''~~) is the MOS {{nowrap|~~(''ar'' ~~+ ''b~~'')~~'''W''' ''c'''''Z'''}} and ''p''~~<~~sub~~>~~'''XZ'''~~</~~sub~~>(~~''s'') is the MOS {{nowrap|(''ar'' + ''~~c'')''~~'W''' ''b~~'''''Y'~~''}}, if either ''b~~'' and ''c'' ~~is divisible by~~ ''r''~~, then the distributions of two of the letters have~~ ''r'' ~~periods~~. ~~Then the distribution~~ of ~~the third letter also has~~ ''r'' ~~periods, meaning that~~ ''s'' ~~itself has~~ ''r'' ~~periods, a contradiction. It suffices to show that {{nowrap|~~''r'' ~~{{=}} 2}}. If {{nowrap|~~''~~r'' > 2}}, then..~~.

(b) The following proof is adapted from "Balanced Sequences and Optimal Routing", by Altman, Gaujal, and Hordijk (2000).

Let ''W'' be the right-infinite word made by concatenating infinitely many copies of ''s''. We use the following steps:

(i) The sequence '''XZX''' must appear in ''W''.

(ii) The sequence '''YXXY''' and '''XYXXYX''' must appear in ''W''.

(iii) The sequence '''XYXZXYX''' appears in ''W''.

(iv) ''W'' = ('''XYXZXYX''')ω.

(c) The scale made by taking ''s'' and conflating '''Y''' and '''Z''' into the letter '''W''' must be a MOS. To this scale we may imagine substituting a scale made of an equal amount of '''Y''' and '''Z''' letters into the "slot letters" '''W''' letter by letter.

For 7.1.2: Suppose ''s'' is balanced and has at least three sizes for ''k''-steps, {{nowrap|''a''''i'''''X''' + ''b''''i'''''Y''' + ''c''''i'''''Z''' {{=}} (''a''''i'', ''b''''i'', ''c''''i'')}} for {{nowrap|''i'' ∈ {{(}}1, 2, 3{{)}}}}. We may assume {{nowrap|(''a''2, ''b''2, ''c''2) {{=}} (''a''1, ''b''1 + 1, ''c''1 − 1)}}. Then either {{nowrap|(''a''3, ''b''3, ''c''3) {{=}} (''a''1 + 1, ''b''1, ''c''1 − 1)}} or {{nowrap|(''a''3, ''b''3, ''c''3) {{=}} (''a''1 − 1, ''b''1 + 1, ''c''1)}}. In both cases, by balancedness applied to subwords of length ''k'', the three vectors represent the only possible interval sizes.

@@ Line 296: / Line 296: @@
 ==== Proof ====
-For 7.1.1: It suffices to show that (a) ternary balanced words are pairwise-MOS and that (b) non-PWF pairwise-MOS scales are even-regular.
+For 7.1.1: We showed previously that the Fraenkel, odd-regular, and even-regular circular words are balanced. Thus it remains to show that (a) ternary balanced words are pairwise-MOS (b) if ''a'' > ''b'' > ''c'', then ''s'' is equivalent to the Fraenkel word (c) assuming ''a'' != ''b'' = ''c'' any ''s'' that is not odd-regular or even-regular is not pairwise-MOS, thus is not balanced.
 (a) Let ''s'' be a ternary balanced word; then for any given letter '''y''' the number of '''y'''s in a subword of any given length ''L'' varies by at most 1. Thus the same is true when we count all non-'''y''' letters in any subword of length ''L''; thus when we equate '''x''' and '''z''', the count of the resulting letter in any subword of length ''L'' differs by 1. Being a binary balanced word is one characterization of the MOS property.
-(b) Assume that the projection ''p''<sub>'''YZ'''</sub>(''s'') identifying '''Y''' and '''Z''' of a primitive PMOS scale ''s'' with signature ''ar'''''X''' ''b'''''Y''' ''c'''''Z'''  is an ''r''-period MOS, {{nowrap|''r'' &gt; 1}}, with step signature ''ar'''''X''' ''dr'''''W'''. We claim that neither ''b'' nor ''c'' is divisible by ''r''. Since ''p''<sub>'''XY'''</sub>(''s'') is the MOS {{nowrap|(''ar'' + ''b'')'''W''' ''c'''''Z'''}} and  ''p''<sub>'''XZ'''</sub>(''s'') is the MOS {{nowrap|(''ar'' + ''c'')'''W''' ''b'''''Y'''}}, if either ''b'' and ''c'' is divisible by ''r'', then the distributions of two of the letters have ''r'' periods. Then the distribution of the third letter also has ''r'' periods, meaning that ''s'' itself has ''r'' periods, a contradiction. It suffices to show that {{nowrap|''r'' {{=}} 2}}. If {{nowrap|''r'' &gt; 2}}, then...
+(b) The following proof is adapted from "Balanced Sequences and Optimal Routing", by Altman, Gaujal, and Hordijk (2000).
+Let ''W'' be the right-infinite word made by concatenating infinitely many copies of ''s''. We use the following steps:
+(i) The sequence '''XZX''' must appear in ''W''.
+(ii) The sequence '''YXXY''' and '''XYXXYX''' must appear in ''W''.
+(iii) The sequence '''XYXZXYX''' appears in ''W''.
+(iv) ''W'' = ('''XYXZXYX''')<sup>ω</sup>.
+(c) The scale made by taking ''s'' and conflating '''Y''' and '''Z''' into the letter '''W''' must be a MOS. To this scale we may imagine substituting a scale made of an equal amount of '''Y''' and '''Z''' letters into the "slot letters" '''W''' letter by letter.
 For 7.1.2: Suppose ''s'' is balanced and has at least three sizes for ''k''-steps, {{nowrap|''a''<sub>''i''</sub>'''X''' + ''b''<sub>''i''</sub>'''Y''' + ''c''<sub>''i''</sub>'''Z''' {{=}} (''a''<sub>''i''</sub>, ''b''<sub>''i''</sub>, ''c''<sub>''i''</sub>)}} for {{nowrap|''i'' ∈ {{(}}1, 2, 3{{)}}}}. We may assume {{nowrap|(''a''<sub>2</sub>, ''b''<sub>2</sub>, ''c''<sub>2</sub>) {{=}} (''a''<sub>1</sub>, ''b''<sub>1</sub> + 1, ''c''<sub>1</sub> − 1)}}. Then either {{nowrap|(''a''<sub>3</sub>, ''b''<sub>3</sub>, ''c''<sub>3</sub>) {{=}} (''a''<sub>1</sub> + 1, ''b''<sub>1</sub>, ''c''<sub>1</sub> − 1)}} or {{nowrap|(''a''<sub>3</sub>, ''b''<sub>3</sub>, ''c''<sub>3</sub>) {{=}} (''a''<sub>1</sub> − 1, ''b''<sub>1</sub> + 1, ''c''<sub>1</sub>)}}. In both cases, by balancedness applied to subwords of length ''k'', the three vectors represent the only possible interval sizes.