Interleaving: Difference between revisions

Line 35:

=== Lemma ===

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.

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

{{proof|contents=Denote by |''w''| the length of subword ''w'' in letters and by ‖''w''‖ the interval subtended by subword ''w'' in its circular word.

{{proof|contents=Denote by {{pipe}}''w''{{pipe}} the length of subword ''w'' in letters and by ‖''w''‖ the interval subtended by subword ''w'' in its circular 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.

Let ''A'' be the set of all (''k'' - 1)/2-step intervals of ''w''. {{pipe}}''A''{{pipe}} = 1 implies that ''k'' = 1 mod {{pipe}}''w''{{pipe}}, so {{pipe}}''A''{{pipe}} ≥ 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 of ''w'' (not intervals) subtending '''w'''1, and ''C'' is the set of all subwords ending in '''Z''' subtending '''w'''2.

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

Choose ''b'' in ''B'' and ''c'' in ''C'' and consider the subwords ''b''('''XZ''', '''YZ''') and ''c''('''XZ''', '''YZ''') of ''S''.

Line 51:

=> either '''XZYZXZ''' or '''YZYZXZ''' occurs (with suffix '''ZYZXZ''')

==> If |''w''| = 3, then these are the whole word ''w''; either way we have four abstract intervals.

==> If {{pipe}}''w''{{pipe}} = 3, then these are the whole word ''w''; either way we have four abstract intervals.

==> If |''w''| > 3, then either '''ZYZXZXZ''' or '''ZYZXZYZ''' occurs (with prefix '''ZYZXZ''').

==> If {{pipe}}''w''{{pipe}} > 3, then either '''ZYZXZXZ''' or '''ZYZXZYZ''' occurs (with prefix '''ZYZXZ''').

Case '''XZYZYZXZ''' => '''XZY''', '''YZY''', '''ZYZ''', '''ZXZ'''

Line 69:

(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 ''w'', hence ''b'' has one more ''x'' and one fewer ''y'' than ''c''.

By scooting ''bx'' one letter to the left in ''w'', 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''.

By scooting ''bx'' one letter to the left in ''w'', we find either (i) ''xb'' or (ii) ''yb''. The {{pipe}}''b''{{pipe}}-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, then same case as (ii), (2).

@@ Line 35: / Line 35: @@
 === Lemma ===
-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.
+If ''S'' consists of the subwords '''XZ''' and '''YZ''' arranged in the pattern of a single-period binary circular word ''w''(''x'', ''y'') where {{pipe}}''w''{{pipe}} > 2, and ''k'' is an odd number greater than 1 and less than {{pipe}}''S''{{pipe}} - 1, then the class of ''k''-steps has more than 3 abstract intervals.
-{{proof|contents=Denote by |''w''| the length of subword ''w'' in letters and by ‖''w''‖ the interval subtended by subword ''w'' in its circular word.
+{{proof|contents=Denote by {{pipe}}''w''{{pipe}} the length of subword ''w'' in letters and by ‖''w''‖ the interval subtended by subword ''w'' in its circular 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>.
+Let ''A'' be the set of all (''k'' - 1)/2-step intervals of ''w''. {{pipe}}''A''{{pipe}} = 1 implies that ''k'' = 1 mod {{pipe}}''w''{{pipe}}, so {{pipe}}''A''{{pipe}} &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 of ''w'' (not intervals) subtending '''w'''<sub>1</sub>, and ''C'' is the set of all subwords ending in '''Z''' subtending '''w'''<sub>2</sub>.
+Say {{pipe}}''A''{{pipe}} = 2. (If {{pipe}}''A''{{pipe}} &ge; 3 then the proof is easy.) Say ''B'' is the set of all subwords of ''w'' (not intervals) subtending '''w'''<sub>1</sub>, and ''C'' is the set of all subwords ending in '''Z''' subtending '''w'''<sub>2</sub>.
 Choose ''b'' in ''B'' and ''c'' in ''C'' and consider the subwords ''b''('''XZ''', '''YZ''') and ''c''('''XZ''', '''YZ''') of ''S''.
@@ Line 51: / Line 51: @@
 => either  '''XZYZXZ''' or '''YZYZXZ''' occurs (with suffix '''ZYZXZ''')
-==> If |''w''| = 3, then these are the whole word ''w''; either way we have four abstract intervals.
+==> If {{pipe}}''w''{{pipe}} = 3, then these are the whole word ''w''; either way we have four abstract intervals.
-==> If |''w''| > 3, then either '''ZYZXZXZ''' or '''ZYZXZYZ''' occurs (with prefix '''ZYZXZ''').
+==> If {{pipe}}''w''{{pipe}} > 3, then either '''ZYZXZXZ''' or '''ZYZXZYZ''' occurs (with prefix '''ZYZXZ''').
 Case '''XZYZYZXZ''' => '''XZY''', '''YZY''', '''ZYZ''', '''ZXZ'''
@@ Line 69: / Line 69: @@
 (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 ''w'', hence ''b'' has one more ''x'' and one fewer ''y'' than ''c''.
-By scooting ''bx'' one letter to the left in ''w'', 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''.
+By scooting ''bx'' one letter to the left in ''w'', we find either (i) ''xb'' or (ii) ''yb''. The {{pipe}}''b''{{pipe}}-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, then same case as (ii), (2).