Fraenkel word: Difference between revisions

Line 20:

{{theorem|name=Lemma|contents=Let ''G''''n'' denote the non-circular Fraenkel word on ''n'' letters. For all ''n'' ≥ 1, 0 ≤ ''i'' ≤ ''n'' − 1, and 1 ≤ {{!}}''w''{{!}} ≤ 2''n''/2 − 2, the following holds for any length-{{!}}''w''{{!}} subword ''w'' of ''G''''n'':

# If {{!}}''w''{{!}} ≡ 0 mod 2''i''+1, then {{!}}''w''{{!}}'''i''' = {{!}}''w''{{!}}/2''i''+1, unless ''w'' is a concatenation of an odd-length suffix of ''G''''n'' and an odd-length prefix of ''G''''n'', in which case {{!}}''w''{{!}}'''i''' = {{!}}''w''{{!}}/2''i''+1 + 1.

# If {{!}}''w''{{!}} ≡ 0 mod 2''i''+1, then {{!}}''w''{{!}}'''i''' = {{!}}''w''{{!}}/2''i''+1

# If {{!}}''w''{{!}} ≢ 0 mod 2''i''+1, then {{!}}''w''{{!}}'''i''' = either floor({{!}}''w''{{!}}/2''i''+1) or ceil({{!}}''w''{{!}}/2''i''+1).

}}

Line 31:

In the second case, if {{!}}''w''{{!}} is odd, If {{!}}''w''{{!}} is even, we treat ''w'' as a word formed with consecutive length-2 subwords for letters, working in the next lower non-circular Fraenkel word, recursively until we reach a word ''v'' of odd length, say in ''G''''n''−''r''. By the inductive hypothesis, ''v'' satisfies {{!}}''v''{{!}}'''j''' = floor({{!}}''v''{{!}}/2''j''+1) or ceil({{!}}''v''{{!}}/2''j''+1) for all ''j'', 0 ≤ j ≤ n − r − 1. This implies that {{!}}''u''{{!}}'''j+r''' = floor({{!}}''u''{{!}}/2''j''+''r''+1) or ceil({{!}}''u''{{!}}/2''j''+''r''+1). For 1 ≤ ''s'' < ''r'', we can apply the first case of the inductive hypothesis to the subword ''v''''s'' corresponding to ''u'' in ''G''''n''−''s'', obtaining {{!}}''v''''s''{{!}}'''0''' = {{!}}''v''''s''{{!}}/2 and hence after substituting back, {{!}}''w''{{!}}'''s''' = {{!}}''w''{{!}}/2''s''+1.}}

TODO: Handle the case where the subword ''w'' of ''F''''n'' is a concatenation of a suffix of ''G''''n'' and a prefix of ''G''''n''.

== Open problems ==

@@ Line 20: / Line 20: @@
 {{theorem|name=Lemma|contents=Let ''G''<sub>''n''</sub> denote the non-circular Fraenkel word on ''n'' letters. For all ''n'' &ge; 1, 0 &le; ''i'' &le; ''n'' &minus; 1, and 1 &le; {{!}}''w''{{!}} &le; 2<sup>''n''/2</sup> &minus; 2, the following holds for any length-{{!}}''w''{{!}} subword ''w'' of ''G''<sub>''n''</sub>:
-# If {{!}}''w''{{!}} ≡ 0 mod 2<sup>''i''+1</sup>, then {{!}}''w''{{!}}<sub>'''i'''</sub> = {{!}}''w''{{!}}/2<sup>''i''+1</sup>, unless ''w'' is a concatenation of an odd-length suffix of ''G''<sub>''n''</sub> and an odd-length prefix of ''G''<sub>''n''</sub>, in which case {{!}}''w''{{!}}<sub>'''i'''</sub> = {{!}}''w''{{!}}/2<sup>''i''+1</sup> + 1.
+# If {{!}}''w''{{!}} ≡ 0 mod 2<sup>''i''+1</sup>, then {{!}}''w''{{!}}<sub>'''i'''</sub> = {{!}}''w''{{!}}/2<sup>''i''+1</sup>
 # If {{!}}''w''{{!}} ≢ 0 mod 2<sup>''i''+1</sup>, then {{!}}''w''{{!}}<sub>'''i'''</sub> = either floor({{!}}''w''{{!}}/2<sup>''i''+1</sup>) or ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>).
 }}
@@ Line 31: / Line 31: @@
 In the second case, if {{!}}''w''{{!}} is odd, If {{!}}''w''{{!}} is even, we treat ''w'' as a word formed with consecutive length-2 subwords for letters, working in the next lower non-circular Fraenkel word, recursively until we reach a word ''v'' of odd length, say in ''G''<sub>''n''&minus;''r''</sub>. By the inductive hypothesis, ''v'' satisfies {{!}}''v''{{!}}<sub>'''j'''</sub> = floor({{!}}''v''{{!}}/2<sup>''j''+1</sup>) or ceil({{!}}''v''{{!}}/2<sup>''j''+1</sup>) for all ''j'', 0 &le; j &le; n &minus; r &minus; 1. This implies that {{!}}''u''{{!}}<sub>'''j+r'''</sub> =  floor({{!}}''u''{{!}}/2<sup>''j''+''r''+1</sup>) or ceil({{!}}''u''{{!}}/2<sup>''j''+''r''+1</sup>). For 1 &le; ''s'' < ''r'', we can apply the first case of the inductive hypothesis to the subword ''v''<sub>''s''</sub> corresponding to ''u'' in ''G''<sub>''n''&minus;''s''</sub>, obtaining {{!}}''v''<sub>''s''</sub>{{!}}<sub>'''0'''</sub> = {{!}}''v''<sub>''s''</sub>{{!}}/2 and hence after substituting back, {{!}}''w''{{!}}<sub>'''s'''</sub> = {{!}}''w''{{!}}/2<sup>''s''+1</sup>.}}
+TODO: Handle the case where the subword ''w'' of ''F''<sub>''n''</sub> is a concatenation of a suffix of ''G''<sub>''n''</sub> and a prefix of ''G''<sub>''n''</sub>.
 == Open problems ==