Ternary scale theorems: Difference between revisions

Line 300:

(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) The following proof is ~~adapted~~ from "Balanced Sequences and Optimal Routing", by Altman, Gaujal, and Hordijk (2000).

(b) The following proof is taken 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''.

There are two consecutive '''X'''s with no '''Y''' in between since ''a'' > ''b''. If '''XX''' appears, then a '''Z''' is necessarily surrounded by two '''X'''s.

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

There exists a pair of consecutive '''Y'''s with no '''Z''' in between. Thus we have a subword of the form '''YX'''''n'''''Y'''. Now, ''n'' ≤ 1 is not possible because of the presence of '''XZX''' and '''Y'''-balance. ''n'' ≥ 3 implies the existence of '''X'''''n''-1'''ZX'''''n''-1 by '''X'''-balance which is incompatible with '''YX'''''n'''''Y''' because of '''Y'''-balance. Therefore, ''n'' = 2. Note that this also implies the presence of subwords '''XX''' and '''XYXXYX'''.

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

The sequence ''W'' must contain a '''Z'''. This '''Z''' is necessarily surrounded by two '''X'''s since '''XX''' exists by Step (ii). This group is necessarily surrounded by two '''Y'''s since '''YXXY''' exists, and consequently, necessarily surrounded by two '''X'''s because '''XYXXYX''' exists. We get the sequence '''XYXZXYX'''.

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

No letter around this word can be a '''Z''' because '''YXXY''' exists. None can be a '''Y''' since '''XZX''' exists. Therefore, they have to be two '''X'''s. Then note that the two surrounding letters cannot be '''Z''' (because of the existence of '''XYXXYX''') nor '''X''' (because of the existence of '''YXZ''') so they are '''Y''', then followed by '''X''' (because '''XX''' exists). At this point, we have the sequence

“_'''XYZXYXZXYX'''_”. Both _s are necessarily '''Z'''s. To end the proof, note that we have obtained the configuration around every '''Z''' and this determines the whole sequence. Thus ''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.

@@ Line 300: / Line 300: @@
 (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) The following proof is adapted from "Balanced Sequences and Optimal Routing", by Altman, Gaujal, and Hordijk (2000).
+(b) The following proof is taken 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''.
+There are two consecutive '''X'''s with no '''Y''' in between since ''a'' > ''b''. If '''XX''' appears, then a '''Z''' is necessarily surrounded by two '''X'''s.
 (ii) The sequence '''YXXY''' and '''XYXXYX''' must appear in ''W''.
+There exists a pair of consecutive '''Y'''s with no '''Z''' in between. Thus we have a subword of the form '''YX'''<sup>''n''</sup>'''Y'''. Now, ''n'' &le; 1 is not possible because of the presence of '''XZX''' and '''Y'''-balance. ''n'' &ge; 3 implies the existence of '''X'''<sup>''n''-1</sup>'''ZX'''<sup>''n''-1</sup> by '''X'''-balance which is incompatible with '''YX'''<sup>''n''</sup>'''Y''' because of '''Y'''-balance. Therefore, ''n'' = 2. Note that this also implies the presence of subwords '''XX''' and '''XYXXYX'''.
 (iii) The sequence '''XYXZXYX''' appears in ''W''.
+The sequence ''W'' must contain a '''Z'''. This '''Z''' is necessarily surrounded by two '''X'''s since '''XX''' exists by Step (ii). This group is necessarily surrounded by two '''Y'''s since '''YXXY''' exists, and consequently, necessarily surrounded by two '''X'''s because '''XYXXYX''' exists. We get the sequence '''XYXZXYX'''.
 (iv) ''W'' = ('''XYXZXYX''')<sup>ω</sup>.
+No letter around this word can be a '''Z''' because '''YXXY''' exists. None can be a '''Y''' since '''XZX''' exists. Therefore, they have to be two '''X'''s. Then note that the two surrounding letters cannot be '''Z''' (because of the existence of '''XYXXYX''') nor '''X''' (because of the existence of '''YXZ''') so they are '''Y''', then followed by '''X''' (because '''XX''' exists). At this point, we have the sequence
+“_'''XYZXYXZXYX'''_”. Both _s are necessarily '''Z'''s. To end the proof, note that we have obtained the configuration around every '''Z''' and this determines the whole sequence. Thus ''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.