Fraenkel word: Difference between revisions

Line 17:

== Facts ==

Below we denote the length of a word ''w'' by |''w''| and the number of occurrences of the letter '''i''' in ''w'' as {{!}}''w''{{!}}'''i''', as is standard notation in combinatorics on words. The notation ''w''(''u''0, ..., ''u''''r''−1) represents the word ''w'' in '''0''', '''1''', ..., '''r−1''' but with '''i''' replaced by the word ''u''''i''.

=== Fraenkel words are balanced ===

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

Line 43:

{{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''.

{{theorem|name=Lemma|contents=Let ''G''''n'' denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of ''G''''n'' such that ''w'' = ''uv'' where ''u'' is a nonempty suffix of ''F''''n'' and ''v'' is a nonempty prefix of ''F''''n''. For 1 ≤ {{!}}''w''{{!}} ≤ 2''n''/2 − 2, either {{!}}''w''{{!}}'''i''' = ceil({{!}}''w''{{!}}/2''i''+1) or ceil({{!}}''w''{{!}}/2''i''+1) − 1.

}}

{{proof|contents=

There are 2 cases:

# Both {{!}}''u''{{!}} and {{!}}''v''{{!}} are 0 mod 2''i''+1.

# At least one of {{!}}''u''{{!}} and {{!}}''v''{{!}} is not 0 mod 2''i''+1.

In case 1, by the preceding lemma {{!}}''u''{{!}}'''i''' = {{!}}''u''{{!}}/2''i''+1 and {{!}}''v''{{!}}'''i''' = {{!}}''v''{{!}}/2''i''+1, and hence {{!}}''w''{{!}}'''i''' = {{!}}''w''{{!}}/2''i''+1 = ceil({{!}}''w''{{!}}/2''i''+1).

In case 2, suppose ''w'' = ''ustv'' where ''st'' is as in case 1 and {{!}}''u''{{!}} and {{!}}''v''{{!}} are less than 2''i''+1. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''''i''; hence {{!}}''u''{{!}}'''i''' = {{!}}''st''{{!}}'''i''' = {{!}}''st''{{!}}/2''i''+1. As {{!}}''u''{{!}} + {{!}}''v''{{!}} ≤ 2''i''+1 − 2, we have {{!}}''w''{{!}}'''i''' ≥ ceil({{!}}''w''{{!}}/2''i''+1) − 1 = {{!}}''st''{{!}}'''i'''. On the other hand, {{!}}''w''{{!}}'''i''' < ceil({{!}}''w''{{!}}/2''i''+1), lest ''u'' or ''v'' have an '''i'''. Therefore {{!}}''w''{{!}}'''i''' = ceil({{!}}''w''{{!}}/2''i''+1) − 1.

}}

== Open problems ==

@@ Line 17: / Line 17: @@
 == Facts ==
 Below we denote the length of a word ''w'' by |''w''| and the number of occurrences of the letter '''i''' in ''w'' as {{!}}''w''{{!}}<sub>'''i'''</sub>, as is standard notation in combinatorics on words. The notation ''w''(''u''<sub>0</sub>, ..., ''u''<sub>''r''&minus;1</sub>) represents the word ''w'' in '''0''', '''1''', ..., '''r&minus;1''' but with '''i''' replaced by the word ''u''<sub>''i''</sub>.
+=== Fraenkel words are balanced ===
 {{theorem|contents=As circular words, Fraenkel words are [[balanced]].}}
@@ Line 43: / Line 43: @@
 {{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>.
+{{theorem|name=Lemma|contents=Let ''G''<sub>''n''</sub> denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of ''G''<sub>''n''</sub> such that ''w'' = ''uv'' where ''u'' is a nonempty suffix of ''F''<sub>''n''</sub> and ''v'' is a nonempty prefix of ''F''<sub>''n''</sub>. For 1 &le; {{!}}''w''{{!}} &le; 2<sup>''n''/2</sup> &minus; 2, either {{!}}''w''{{!}}<sub>'''i'''</sub> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) or ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) &minus; 1.
+}}
+{{proof|contents=
+There are 2 cases:
+# Both {{!}}''u''{{!}} and {{!}}''v''{{!}} are 0 mod 2<sup>''i''+1</sup>.
+# At least one of {{!}}''u''{{!}} and {{!}}''v''{{!}} is not 0 mod 2<sup>''i''+1</sup>.
+In case 1, by the preceding lemma {{!}}''u''{{!}}<sub>'''i'''</sub> = {{!}}''u''{{!}}/2<sup>''i''+1</sup> and {{!}}''v''{{!}}<sub>'''i'''</sub> = {{!}}''v''{{!}}/2<sup>''i''+1</sup>, and hence {{!}}''w''{{!}}<sub>'''i'''</sub> = {{!}}''w''{{!}}/2<sup>''i''+1</sup> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>).
+In case 2, suppose ''w'' = ''ustv'' where ''st'' is as in case 1 and {{!}}''u''{{!}} and {{!}}''v''{{!}} are less than 2<sup>''i''+1</sup>. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''<sub>''i''</sub>; hence {{!}}''u''{{!}}<sub>'''i'''</sub> = {{!}}''st''{{!}}<sub>'''i'''</sub> = {{!}}''st''{{!}}/2<sup>''i''+1</sup>. As {{!}}''u''{{!}} + {{!}}''v''{{!}} &le; 2<sup>''i''+1</sup> &minus; 2, we have {{!}}''w''{{!}}<sub>'''i'''</sub> &ge; ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) &minus; 1 = {{!}}''st''{{!}}<sub>'''i'''</sub>. On the other hand, {{!}}''w''{{!}}<sub>'''i'''</sub> < ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>), lest ''u'' or ''v'' have an '''i'''. Therefore {{!}}''w''{{!}}<sub>'''i'''</sub> = ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>) &minus; 1.
+}}
 == Open problems ==