Interleaving: Difference between revisions

Line 37:

If ''S'' consists of the subwords '''XZ''' and '''YZ''' arranged in the pattern of a single-period binary circular word ''w''(''x'', ''y'') where |''w''| > 2, and ''k'' is an odd number greater than 1 and less than |''S''| - 1, then the class of ''k''-steps has more than 3 abstract intervals.

Proof: Let ''A'' be the set of all (''k'' - 1)/2-step intervals of ''w''. |''A''| = 1 implies that ''k'' = 1 mod |''w''|, so |''A''| ≥ 2 and contains at least two intervals '''w'''1 and '''w'''2.

Proof: Denote by |w| the length of ''w'' in letters and by ||''w''|| the interval subtended by ''w'' in its scale word.

Let ''A'' be the set of all (''k'' - 1)/2-step intervals of ''w''. |''A''| = 1 implies that ''k'' = 1 mod |''w''|, so |''A''| ≥ 2 and contains at least two intervals '''w'''1 and '''w'''2.

Say |''A''| = 2. (If |''A''| ≥ 3 then the proof is easy.) Say ''B'' is the set of all subwords (not intervals) subtending '''w'''1, and ''C'' is the set of all subwords ending in '''Z''' subtending '''w'''2.

Line 65:

Line 67:

For any other ''k'', we similarly go through the cases (a) ''bx'' and ''cx'', (b) ''bx'' and ''cy'', (c) ''by'' and ''cx'', (d) ''by'' and ''cy''.

(a) '''Z'''b('''XZ''', '''YZ'''), '''Z'''c('''XZ''', '''YZ'''), b('''XZ''', '''YZ''')'''X''', c('''XZ''', '''YZ''')'''X''' => done

(a) '''Z'''''b''('''XZ''', '''YZ'''), '''Z'''''c''('''XZ''', '''YZ'''), ''b''('''XZ''', '''YZ''')'''X''', ''c''('''XZ''', '''YZ''')'''X''' => done

(d) is similar to (a).

(b) We have '''Z'''''b''('''XZ''', '''YZ'''), '''Z'''''c''('''XZ''', '''YZ'''), ''b''('''XZ''', '''YZ''')'''X''' and ''c''('''XZ''', '''YZ''')'''Y'''. If the sizes of ''b''('''XZ''', '''YZ''')'''X''' and ''c''('''XZ''', '''YZ''')'''Y''' are different we are done. If they are the same, we have that ''bx'' and ''cy'' subtend the same interval in ''s'', hence ''b'' has one more ''x'' and one fewer ''y'' than ''c''.

By scooting ''bx'' one letter to the left in ''s'', we find either (i) ''xb'' or (ii) ''yb''. The |''b''|-letter prefix ''p'' of this subword subtends either the same interval as (1) ''b'' or (2) ''c''.

(i), (1) => ''b'' = ''b'x'', ''p'' = ''xb' '', have ''xbx'' = ''xb'xx'', continue scooting to the left until you find a ''y'' to the left

(ii), (1) => ''b'' = ''b'y'', ''p'' = ''yb' '', we have ||''p''('''XZ''', '''YZ''')'''Y'''|| as a fourth interval size.

(d) ~~is similar to~~ (a)

(i), (2) => ''b'' = ''b'y'', ''p'' = ''xb' '', we have ||''p''('''XZ''', '''YZ''')'''X'''|| as a fourth interval size.

(b) ~~We have '''Z'''b~~(~~'''XZ''', '''YZ'''~~)~~, '''Z'''c(~~'''XZ'''~~, '''YZ'''),~~ b~~('''XZ~~''', '''YZ'''~~)'''X''' and c('''XZ~~''', ''~~'YZ'~~''~~)'''Y'''. If the sizes of b~~('''XZ''', '''YZ''')'''X''' ~~and c('''XZ''', '''YZ''')'''Y''' are different we are done. If they are the same, we have that ''bx'' and ''cy'' subtend the same~~ interval ~~in ''s'', hence ''b'' has one more ''x'' and one fewer ''y'' than ''c''~~.

(ii), (2) => ''b'' =''b'x'', ''p'' = ''yb' '', we have ||''p''('''XZ''', '''YZ''')'''X'''|| as a fourth interval size.

(c) is similar to (b)

(c) is similar to (b).

=== Proof of Theorem ===

@@ Line 37: / Line 37: @@
 If ''S'' consists of the subwords '''XZ''' and '''YZ''' arranged in the pattern of a single-period binary circular word ''w''(''x'', ''y'') where |''w''| > 2, and ''k'' is an odd number greater than 1 and less than |''S''| - 1, then the class of ''k''-steps has more than 3 abstract intervals.
-Proof: Let ''A'' be the set of all (''k'' - 1)/2-step intervals of ''w''. |''A''| = 1 implies that ''k'' = 1 mod |''w''|, so |''A''| &ge; 2 and contains at least two intervals '''w'''<sub>1</sub> and '''w'''<sub>2</sub>.
+Proof: Denote by |w| the length of ''w'' in letters and by ||''w''|| the interval subtended by ''w'' in its scale word.
+Let ''A'' be the set of all (''k'' - 1)/2-step intervals of ''w''. |''A''| = 1 implies that ''k'' = 1 mod |''w''|, so |''A''| &ge; 2 and contains at least two intervals '''w'''<sub>1</sub> and '''w'''<sub>2</sub>.
 Say |''A''| = 2. (If |''A''| &ge; 3 then the proof is easy.) Say ''B'' is the set of all subwords (not intervals) subtending '''w'''<sub>1</sub>, and ''C'' is the set of all subwords ending in '''Z''' subtending '''w'''<sub>2</sub>.
@@ Line 65: / Line 67: @@
 For any other ''k'', we similarly go through the cases (a) ''bx'' and ''cx'', (b) ''bx'' and ''cy'', (c) ''by'' and ''cx'', (d) ''by'' and ''cy''.
-(a) '''Z'''b('''XZ''', '''YZ'''), '''Z'''c('''XZ''', '''YZ'''), b('''XZ''', '''YZ''')'''X''', c('''XZ''', '''YZ''')'''X''' => done
+(a) '''Z'''''b''('''XZ''', '''YZ'''), '''Z'''''c''('''XZ''', '''YZ'''), ''b''('''XZ''', '''YZ''')'''X''', ''c''('''XZ''', '''YZ''')'''X''' => done
+(d) is similar to (a).
+(b) We have '''Z'''''b''('''XZ''', '''YZ'''), '''Z'''''c''('''XZ''', '''YZ'''), ''b''('''XZ''', '''YZ''')'''X''' and ''c''('''XZ''', '''YZ''')'''Y'''. If the sizes of ''b''('''XZ''', '''YZ''')'''X''' and ''c''('''XZ''', '''YZ''')'''Y''' are different we are done. If they are the same, we have that ''bx'' and ''cy'' subtend the same interval in ''s'', hence ''b'' has one more ''x'' and one fewer ''y'' than ''c''.
+By scooting ''bx'' one letter to the left in ''s'', we find either (i) ''xb'' or (ii) ''yb''. The |''b''|-letter prefix ''p'' of this subword subtends either the same interval as (1) ''b'' or (2) ''c''.
+(i), (1) => ''b'' = ''b'x'', ''p'' = ''xb' '', have ''xbx'' = ''xb'xx'', continue scooting to the left until you find a ''y'' to the left
+(ii), (1) => ''b'' = ''b'y'', ''p'' = ''yb' '', we have ||''p''('''XZ''', '''YZ''')'''Y'''|| as a fourth interval size.
-(d) is similar to (a)
+(i), (2) => ''b'' = ''b'y'', ''p'' = ''xb' '', we have ||''p''('''XZ''', '''YZ''')'''X'''|| as a fourth interval size.
-(b) We have '''Z'''b('''XZ''', '''YZ'''), '''Z'''c('''XZ''', '''YZ'''), b('''XZ''', '''YZ''')'''X''' and c('''XZ''', '''YZ''')'''Y'''. If the sizes of b('''XZ''', '''YZ''')'''X''' and c('''XZ''', '''YZ''')'''Y''' are different we are done. If they are the same, we have that ''bx'' and ''cy'' subtend the same interval in ''s'', hence ''b'' has one more ''x'' and one fewer ''y'' than ''c''.
+(ii), (2) => ''b'' =''b'x'', ''p'' = ''yb' '', we have ||''p''('''XZ''', '''YZ''')'''X'''|| as a fourth interval size.
-(c) is similar to (b)
+(c) is similar to (b).
 === Proof of Theorem ===