Fraenkel word: Difference between revisions

Line 13:

Fraenkel words are named after mathematician Aviezri S. Fraenkel.

== Facts ==

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

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=For all ''n'' ≥ 1, the ''n''-ary Fraenkel word is [[balanced]] as a circular word.}}

~~TODO~~: proof

To prove this, we prove the following lemmas by induction on ''n'':

{{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''' = either floor({{!}}''w''{{!}}/2''i''+1) or ceil({{!}}''w''{{!}}/2''i''+1).

}}

{{proof|contents=Assume first that ''w'' is a subword of ''G''''n''. In the first case, it has the form

<math> w = u(\mathbf{1}^\prime, \mathbf{2}^\prime, ..., \mathbf{(n-1)}^\prime),</math>

where ''u'' is a subword of ''G''''n''− 1 with 1 ≤ {{!}}''u''{{!}} ≤ 2''n''−1 − 2 and <math>\mathbf{j}^\prime</math> denotes either '''0j''' (for all ''j'', 0 < ''j'' < n) or '''j0''' (for all ''j'', 0 < ''j'' < ''n''). In particular, {{!}}''w''{{!}}'''0''' = {{!}}''w''{{!}}/2. Since {{!}}''u''{{!}} ≡ 0 mod 2''i'', by the inductive hypothesis applied to subwords of ''F''''n''−1 we have {{!}}''w''{{!}}/2''i''+1 = {{!}}''u''{{!}}/2''i'' = {{!}}''u''{{!}}'''i−1''' = {{!}}''w''{{!}}'''i''' for 1 ≤ ''i'' ≤ ''n'' − 1, as desired.

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.}}

== Open problems ==

@@ Line 13: / Line 13: @@
 Fraenkel words are named after mathematician Aviezri S. Fraenkel.
 == Facts ==
-{{theorem|contents=As circular words, Fraenkel words are [[balanced]].}}
+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=For all ''n'' &ge; 1, the ''n''-ary Fraenkel word is [[balanced]] as a circular word.}}
-TODO: proof
+To prove this, we prove the following lemmas by induction on ''n'':
+{{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> = either floor({{!}}''w''{{!}}/2<sup>''i''+1</sup>) or ceil({{!}}''w''{{!}}/2<sup>''i''+1</sup>).
+}}
+{{proof|contents=Assume first that ''w'' is a subword of ''G''<sub>''n''</sub>. In the first case, it has the form
+<math> w = u(\mathbf{1}^\prime, \mathbf{2}^\prime, ..., \mathbf{(n-1)}^\prime),</math>
+where ''u'' is a subword of ''G''<sub>''n''&minus; 1</sub> with 1 &le; {{!}}''u''{{!}} &le; 2<sup>''n''&minus;1</sup> &minus; 2 and <math>\mathbf{j}^\prime</math> denotes either '''0j''' (for all ''j'', 0 < ''j'' < n) or '''j0''' (for all ''j'', 0 < ''j'' < ''n''). In particular, {{!}}''w''{{!}}<sub>'''0'''</sub> = {{!}}''w''{{!}}/2. Since {{!}}''u''{{!}} ≡ 0 mod 2<sup>''i''</sup>, by the inductive hypothesis applied to subwords of ''F''<sub>''n''&minus;1</sub> we have {{!}}''w''{{!}}/2<sup>''i''+1</sup> = {{!}}''u''{{!}}/2<sup>''i''</sup> = {{!}}''u''{{!}}<sub>'''i&minus;1'''</sub> = {{!}}''w''{{!}}<sub>'''i'''</sub> for 1 &le; ''i'' &le; ''n'' &minus; 1, as desired.
+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>.}}
 == Open problems ==