Fraenkel word: Difference between revisions

Line 15:

{{theorem|contents=As circular words, Fraenkel words are [[balanced]].}}

TODO: ~~proof~~

The theorem will be a consequence of the following lemmas:

{{theorem|name=Lemma|contents=Let ''F''''n'' denote the non-circular Fraenkel word on ''n'' letters. For ''n'' ≥ 1 and 0 ≤ ''i'' ≤ ''n'' − 1, the letter '''i''' appears every 2''i''+1 letters in ''F''''n''; i.e. in a subword of the form '''i'''''w'''''i''', {{!}}''w''{{!}} = 2''i''+1 − 1.}}

{{proof|contents=We prove this by induction on ''n''. The ''n'' = 1 case being trivial, for ''n'' > 1 we start by observing that '''i''' always occurs as the greatest letter of a subword that is the Fraenkel word ''F''''i''+1, and ''F''''i''+1 is always flanked by letters that are greater. This subword '''i'''''F''''i'' is not a suffix of ''F''''n'', and we thus have

'''i'''''F''''i'''''k'''...

where ''k'' > ''i'', and ''F''0 is the empty word. Since '''k''' occurs as the middle letter of ''F''''k''+1, there is a copy of ''F''''k'' that follows '''k'''; ''F''''k'' has ''F''i as a prefix. Thus ''F''''n'' has a subword

'''i'''''F''i'''k'''''F''i'''i''',

as desired, since {{!}}''F''i'''i'''{{!}} = 2''i'' − 1.

}}

{{theorem|name=Lemma|contents=For all ''n'' ≥ 1, 0 ≤ ''i'' ≤ ''n'' − 1, and 1 ≤ {{!}}''w''{{!}} ≤ 2''n''/2 − 2, the following holds for any subword ''w'' of ''F''''n'':

# 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).

#* More precisely, if for a given ''i'' we have ''w'' = ''uv'' or ''vu'' where ''u'' is a possibly empty word whose length is 0 mod 2''i''+1, and ''v'' intersects the middle of an ''F''''i''+1, then {{!}}''w''{{!}}'''i''' = ceil({{!}}''w''{{!}}/2''i''+1). Otherwise, {{!}}''w''{{!}}'''i''' = floor({{!}}''w''{{!}}/2''i''+1).

}}

{{proof|contents=We use the previous lemma. In the first case, ''w'' is guaranteed to have exactly ''k''-many '''i'''s where {{!}}''w''{{!}} = ''k''2''i''+1. In the second case, if ''k''2''i''+1 < {{!}}''w''{{!}} < (''k'' + 1)2''i''+1 and ''w'' = ''uv'' or ''vu'' where {{!}}''u''{{!}} ≡ 0 mod 2''i''+1, then ''u'' satisfies {{!}}''u''{{!}}'''i''' = ''k''2''i''+1/2''i''+1 = ''k'' by the previous case. Thus {{!}}''w''{{!}}'''i''' is determined by {{!}}''v''{{!}}'''i''', which is 1 if ''v'' contains the '''i''' in the middle of ''F''''i'', implying {{!}}''w''{{!}}'''i''' = ceil({{!}}''w''{{!}}/2''i''+1), and 0 otherwise, implying {{!}}''w''{{!}}'''i''' = floor({{!}}''w''{{!}}/2''i''+1).}}

TODO: A final lemma handling the case where the subword ''w'' of ''F''''n'' is a concatenation of a suffix of ''F''''n'' and a prefix of ''F''''n''.

== Open problems ==

@@ Line 15: / Line 15: @@
 {{theorem|contents=As circular words, Fraenkel words are [[balanced]].}}
-TODO: proof
+The theorem will be a consequence of the following lemmas:
+{{theorem|name=Lemma|contents=Let ''F''<sub>''n''</sub> denote the non-circular Fraenkel word on ''n'' letters. For ''n'' &ge; 1 and 0 &le; ''i'' &le; ''n'' &minus; 1, the letter '''i''' appears every 2<sup>''i''+1</sup> letters in ''F''<sub>''n''</sub>; i.e. in a subword of the form '''i'''''w'''''i''', {{!}}''w''{{!}} = 2<sup>''i''+1</sup> &minus; 1.}}
+{{proof|contents=We prove this by induction on ''n''. The ''n'' = 1 case being trivial, for ''n'' > 1 we start by observing that '''i''' always occurs as the greatest letter of a subword that is the Fraenkel word ''F''<sub>''i''+1</sub>, and ''F''<sub>''i''+1</sub> is always flanked by letters that are greater. This subword  '''i'''''F''<sub>''i''</sub> is not a suffix of ''F''<sub>''n''</sub>, and we thus have
+'''i'''''F''<sub>''i''</sub>'''k'''...
+where ''k'' > ''i'', and ''F''<sub>0</sub> is the empty word. Since '''k''' occurs as the middle letter of ''F''<sub>''k''+1</sub>, there is a copy of ''F''<sub>''k''</sub> that follows '''k'''; ''F''<sub>''k''</sub> has ''F''<sub>i</sub> as a prefix. Thus ''F''<sub>''n''</sub> has a subword
+'''i'''''F''<sub>i</sub>'''k'''''F''<sub>i</sub>'''i''',
+as desired, since {{!}}''F''<sub>i</sub>'''i'''{{!}} = 2<sup>''i''</sup> &minus; 1.
+}}
+{{theorem|name=Lemma|contents=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 subword ''w'' of ''F''<sub>''n''</sub>:
+# 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>).
+#* More precisely, if for a given ''i'' we have ''w'' = ''uv'' or ''vu'' where ''u'' is a possibly empty word whose length is 0 mod 2<sup>''i''+1</sup>, and ''v'' intersects the middle of an ''F''<sub>''i''+1</sub>, then {{!}}''w''{{!}}<sub>'''i'''</sub> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>). Otherwise, {{!}}''w''{{!}}<sub>'''i'''</sub> = floor({{!}}''w''{{!}}/2<sup>''i''+1</sup>).
+}}
+{{proof|contents=We use the previous lemma. In the first case, ''w'' is guaranteed to have exactly ''k''-many '''i'''s where {{!}}''w''{{!}} = ''k''2<sup>''i''+1</sup>. In the second case, if ''k''2<sup>''i''+1</sup> < {{!}}''w''{{!}} < (''k'' + 1)2<sup>''i''+1</sup> and ''w'' = ''uv'' or ''vu'' where {{!}}''u''{{!}} ≡ 0 mod 2<sup>''i''+1</sup>,  then ''u'' satisfies {{!}}''u''{{!}}<sub>'''i'''</sub> = ''k''2<sup>''i''+1</sup>/2<sup>''i''+1</sup> = ''k'' by the previous case. Thus {{!}}''w''{{!}}<sub>'''i'''</sub>  is determined by {{!}}''v''{{!}}<sub>'''i'''</sub>, which is 1 if ''v'' contains the '''i''' in the middle of ''F''<sub>''i''</sub>, implying {{!}}''w''{{!}}<sub>'''i'''</sub> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>), and 0 otherwise, implying {{!}}''w''{{!}}<sub>'''i'''</sub> = floor({{!}}''w''{{!}}/2<sup>''i''+1</sup>).}}
+TODO: A final lemma handling the case where the subword ''w'' of ''F''<sub>''n''</sub> is a concatenation of a suffix of ''F''<sub>''n''</sub> and a prefix of ''F''<sub>''n''</sub>.
 == Open problems ==