Fraenkel word: Difference between revisions

Line 52:

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.

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 0 < {{!}}''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.

}}

@@ Line 52: / Line 52: @@
 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.
+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 0 < {{!}}''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.
 }}