Fraenkel word - Revision history

ArrowHead294 at 15:49, 17 April 2025

2025-04-17T15:49:56Z

ArrowHead294 at 13:13, 19 March 2025

2025-03-19T13:13:10Z

Show changes

Inthar at 00:04, 16 February 2024

2024-02-16T00:04:22Z

← Older revision		Revision as of 00:04, 16 February 2024
Line 25:		Line 25:
	{{theorem\|name=Lemma\|contents=Let ''F''<sub>''n''</sub> denote the non-circular Fraenkel word on ''n'' letters. For ''n'' ≥ 1 and 0 ≤ ''i'' ≤ ''n'' − 1, the letter '''i''' appears once every 2<sup>''i''+1</sup> letters in ''F''<sub>''n''</sub>; i.e. in every subword of the form '''i'''''w'''''i''', {{!}}''w''{{!}} = 2<sup>''i''+1</sup> − 1.}}		{{theorem\|name=Lemma\|contents=Let ''F''<sub>''n''</sub> denote the non-circular Fraenkel word on ''n'' letters. For ''n'' ≥ 1 and 0 ≤ ''i'' ≤ ''n'' − 1, the letter '''i''' appears once every 2<sup>''i''+1</sup> letters in ''F''<sub>''n''</sub>; i.e. in every subword of the form '''i'''''w'''''i''', {{!}}''w''{{!}} = 2<sup>''i''+1</sup> − 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		{{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 (on at least one side) 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'''...		'''i'''''F''<sub>''i''</sub>'''k'''...

Inthar: /* Fraenkel words are balanced */

2024-02-16T00:03:28Z

Fraenkel words are balanced

← Older revision		Revision as of 00:03, 16 February 2024
Line 31:		Line 31:
	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		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''',		'''i'''''F''<sub>''i''</sub>'''k'''''F''<sub>''i''</sub>'''i''',

	as desired, since {{!}}''F''<sub>i</sub>{{!}} = 2<sup>''i''</sup> − 1.		as desired, since {{!}}''F''<sub>i</sub>{{!}} = 2<sup>''i''</sup> − 1.

Inthar: /* Other conjectures */Period

2024-02-16T00:01:12Z

Other conjectures: Period

← Older revision		Revision as of 00:01, 16 February 2024
Line 81:		Line 81:
	G_3 &= \mathbf{01010201010201010}, \\		G_3 &= \mathbf{01010201010201010}, \\
	&\ \ \vdots \\		&\ \ \vdots \\
	G_{n} &= G_{n-1}(\mathbf{n-1})G_{n-1}(\mathbf{n-1})G_{n-1},		G_{n} &= G_{n-1}(\mathbf{n-1})G_{n-1}(\mathbf{n-1})G_{n-1}.
	\end{align*}}		\end{align*}}
	</math>		</math>

Inthar at 23:56, 15 February 2024

2024-02-15T23:56:33Z

← Older revision		Revision as of 23:56, 15 February 2024
Line 12:		Line 12:
	</math>		</math>

	where ε is the empty word. Fraenkel words ~~are frequently~~ encountered as exceptional examples of scale properties alongside larger families, e.g. for the [[interval variety\|maximum/strict variety]] 3 and [[balance]] properties.		where ε is the empty word. Fraenkel words may be encountered as exceptional examples of scale properties alongside larger families, e.g. for the [[interval variety\|maximum/strict variety]] 3 and [[balance]] properties.

	Fraenkel words are named after mathematician Aviezri S. Fraenkel.		Fraenkel words are named after mathematician Aviezri S. Fraenkel.

Akselai: /* Open problems */

2024-02-15T20:32:32Z

Open problems

@@ Line 69: / Line 69: @@
 === Other conjectures ===
 '''Conjecture:''' Let MV(''s'') denote the [[maximum variety]] of the circular word ''s''. Then {MV(''F''<sub>2''k''&minus;1</sub>), MV(''F''<sub>2''k''</sub>), MV(''F''<sub>2''k''+1</sub>)} is an arithmetic progression with common difference ''f''<sub>2''k''</sub> (the 2''k''-th Fibonacci number: 1, 3, 8, 21, ...) for every ''k'' &ge; 1.
 == See also ==

Inthar: /* Other conjectures */

2024-02-15T19:00:05Z

Other conjectures

← Older revision		Revision as of 19:00, 15 February 2024
Line 68:		Line 68:
	For [[circular word]]s (equivalently, infinite periodic words), '''Fraenkel's conjecture''' asserts that the only [[balanced]] circular words over ''n'' ≥ 3 letters with letter occurrences pairwise distinct are (letter reassignments of) <math>F_n.</math><ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> The conjecture is known to be true for 3 ≤ ''n'' ≤ 7.		For [[circular word]]s (equivalently, infinite periodic words), '''Fraenkel's conjecture''' asserts that the only [[balanced]] circular words over ''n'' ≥ 3 letters with letter occurrences pairwise distinct are (letter reassignments of) <math>F_n.</math><ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> The conjecture is known to be true for 3 ≤ ''n'' ≤ 7.
	=== Other conjectures ===		=== Other conjectures ===
	'''Conjecture:''' Let MV(''s'') denote the [[maximum variety]] of the circular word ''s''. Then {MV(''F''<sub>2''k''−1</sub>), MV(''F''<sub>2''k''</sub>), MV(''F''<sub>2''k''+1</sub>)} is an arithmetic progression with common difference ''f''<sub>''k''+1</sub> (the (''k'' ~~+ 1)~~-st Fibonacci number) for every ''k'' ≥ 1.		'''Conjecture:''' Let MV(''s'') denote the [[maximum variety]] of the circular word ''s''. Then {MV(''F''<sub>2''k''−1</sub>), MV(''F''<sub>2''k''</sub>), MV(''F''<sub>2''k''+1</sub>)} is an arithmetic progression with common difference ''f''<sub>2''k''</sub> (the 2''k''-th Fibonacci number: 1, 3, 8, 21, ...) for every ''k'' ≥ 1.

	== See also ==		== See also ==

Inthar: /* Other conjectures */

2024-02-15T18:55:39Z

Other conjectures

← Older revision		Revision as of 18:55, 15 February 2024
Line 68:		Line 68:
	For [[circular word]]s (equivalently, infinite periodic words), '''Fraenkel's conjecture''' asserts that the only [[balanced]] circular words over ''n'' ≥ 3 letters with letter occurrences pairwise distinct are (letter reassignments of) <math>F_n.</math><ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> The conjecture is known to be true for 3 ≤ ''n'' ≤ 7.		For [[circular word]]s (equivalently, infinite periodic words), '''Fraenkel's conjecture''' asserts that the only [[balanced]] circular words over ''n'' ≥ 3 letters with letter occurrences pairwise distinct are (letter reassignments of) <math>F_n.</math><ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> The conjecture is known to be true for 3 ≤ ''n'' ≤ 7.
	=== Other conjectures ===		=== Other conjectures ===
	'''Conjecture:''' Let MV(''s'') denote the [[maximum variety]] of the circular word ''s''. Then {MV(''F''<sub>2''k''−1</sub>), MV(''F''<sub>2''k''</sub>), MV(''F''<sub>2''k''+1</sub>)} is an arithmetic progression with common difference ''f''<sub>''k''</sub> (the ''k''th Fibonacci number) for every ''k'' ≥ 1.		'''Conjecture:''' Let MV(''s'') denote the [[maximum variety]] of the circular word ''s''. Then {MV(''F''<sub>2''k''−1</sub>), MV(''F''<sub>2''k''</sub>), MV(''F''<sub>2''k''+1</sub>)} is an arithmetic progression with common difference ''f''<sub>''k''+1</sub> (the (''k'' + 1)-st Fibonacci number) for every ''k'' ≥ 1.

	== See also ==		== See also ==

Inthar: /* Other conjectures */

2024-02-15T18:52:29Z

Other conjectures

← Older revision		Revision as of 18:52, 15 February 2024
Line 68:		Line 68:
	For [[circular word]]s (equivalently, infinite periodic words), '''Fraenkel's conjecture''' asserts that the only [[balanced]] circular words over ''n'' ≥ 3 letters with letter occurrences pairwise distinct are (letter reassignments of) <math>F_n.</math><ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> The conjecture is known to be true for 3 ≤ ''n'' ≤ 7.		For [[circular word]]s (equivalently, infinite periodic words), '''Fraenkel's conjecture''' asserts that the only [[balanced]] circular words over ''n'' ≥ 3 letters with letter occurrences pairwise distinct are (letter reassignments of) <math>F_n.</math><ref>Bulgakova, D. V., Buzhinsky, N., & Goncharov, Y. O. (2023). On balanced and abelian properties of circular words over a ternary alphabet. Theoretical Computer Science, 939, 227-236.</ref> The conjecture is known to be true for 3 ≤ ''n'' ≤ 7.
	=== Other conjectures ===		=== Other conjectures ===
	'''Conjecture:''' Let MV(''s'') denote the [[maximum variety]] of the circular word ''s''. Then {MV(''F''<sub>2''k''−1</sub>), MV(''F''<sub>2''k''</sub>), MV(''F''<sub>2''k''+1</sub>)} is an arithmetic progression for every ''k'' ≥ 1.		'''Conjecture:''' Let MV(''s'') denote the [[maximum variety]] of the circular word ''s''. Then {MV(''F''<sub>2''k''−1</sub>), MV(''F''<sub>2''k''</sub>), MV(''F''<sub>2''k''+1</sub>)} is an arithmetic progression with common difference ''f''<sub>''k''</sub> (the ''k''th Fibonacci number) for every ''k'' ≥ 1.

	== See also ==		== See also ==

← Older revision		Revision as of 15:49, 17 April 2025
Line 17:		Line 17:

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

	=== Fraenkel words are balanced ===		=== Fraenkel words are balanced ===
Line 39:		Line 39:
	{{theorem\|name=Lemma\|contents=For all {{nowrap\|''n'' ≥ 1\|0 ≤ ''i'' ≤ ''n'' − 1}}, and {{nowrap\|1 ≤ {{abs\|''w''}} ≤ 2<sup>''n''/2</sup> − 2}}, the following holds for any subword ''w'' of ''F''<sub>''n''</sub>:		{{theorem\|name=Lemma\|contents=For all {{nowrap\|''n'' ≥ 1\|0 ≤ ''i'' ≤ ''n'' − 1}}, and {{nowrap\|1 ≤ {{abs\|''w''}} ≤ 2<sup>''n''/2</sup> − 2}}, the following holds for any subword ''w'' of ''F''<sub>''n''</sub>:
	# If {{nowrap\|{{abs\|''w''}} ≡ 0 (mod 2<sup>''i'' + 1</sup>)}}, then {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{abs\|''w''}}/2<sup>''i'' + 1</sup>}}.		# If {{nowrap\|{{abs\|''w''}} ≡ 0 (mod 2<sup>''i'' + 1</sup>)}}, then {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{abs\|''w''}}/2<sup>''i'' + 1</sup>}}.
	# If {{nowrap\|{{abs\|''w''}} ≢ 0 (mod 2<sup>''i'' + 1</sup>)}}, then {{abs\|''w''}}<sub>'''i'''</sub> {{=}} either {{nowrap\|{{floor\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>}}}} or {{nowrap\|{{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>}}}}.		# If {{nowrap\|{{abs\|''w''}} ≢ 0 (mod 2<sup>''i'' + 1</sup>)}}, then {{abs\|''w''}}<sub>'''i'''</sub> {{=}} either {{nowrap\|{{floor\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>\|1.75}}}} or {{nowrap\|{{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>\|1.75}}}}.
	#* More precisely, if for a given ''i'' we have {{nowrap\|''w'' {{=}} ''uv''}} or ''vu'' where ''u'' is a possibly empty word whose length is {{nowrap\|0 (mod 2<sup>''i'' + 1</sup>)}}, and ''v'' is a nonempty word intersecting the middle of an {{nowrap\|''F''<sub>''i'' + 1</sub>}}, then {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>}}}}. Otherwise, {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{floor\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>}}}}.		#* More precisely, if for a given ''i'' we have {{nowrap\|''w'' {{=}} ''uv''}} or ''vu'' where ''u'' is a possibly empty word whose length is {{nowrap\|0 (mod 2<sup>''i'' + 1</sup>)}}, and ''v'' is a nonempty word intersecting the middle of an {{nowrap\|''F''<sub>''i'' + 1</sub>}}, then {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>\|1.75}}}}. Otherwise, {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{floor\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>\|1.75}}}}.
	}}		}}

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

	{{theorem\|name=Lemma\|contents=Let [''F''<sub>''n''</sub>] denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of [''F''<sub>''n''</sub>] such that {{nowrap\|''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 {{nowrap\|1 ≤ {{abs\|''w''}} ≤ 2<sup>''n''/2</sup> − 2}}, either {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>}}}} or {{nowrap\|{{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>}} − 1}}.		{{theorem\|name=Lemma\|contents=Let [''F''<sub>''n''</sub>] denote the circular Fraenkel word on ''n'' letters. Suppose ''w'' is a proper subword of [''F''<sub>''n''</sub>] such that {{nowrap\|''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 {{nowrap\|1 ≤ {{abs\|''w''}} ≤ 2<sup>''n''/2</sup> − 2}}, either {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>\|1.75}}}} or {{nowrap\|{{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>\|1.75}} − 1}}.
	}}		}}

Line 52:		Line 52:
	# Both {{abs\|''u''}} and {{abs\|''v''}} are {{nowrap\|0 (mod 2<sup>''i'' + 1</sup>)}}.		# Both {{abs\|''u''}} and {{abs\|''v''}} are {{nowrap\|0 (mod 2<sup>''i'' + 1</sup>)}}.
	# At least one of {{abs\|''u''}} and {{abs\|''v''}} is not {{nowrap\|0 (mod 2<sup>''i'' + 1</sup>)}}.		# At least one of {{abs\|''u''}} and {{abs\|''v''}} is not {{nowrap\|0 (mod 2<sup>''i'' + 1</sup>)}}.
	In case 1, by the preceding lemma {{nowrap\|{{abs\|''u''}}<sub>'''i'''</sub> {{=}} {{abs\|''u''}}/2<sup>''i'' + 1</sup>}} and {{nowrap\|{{abs\|''v''}}<sub>'''i'''</sub> {{=}} {{abs\|''v''}}/2<sup>''i'' + 1</sup>}}, and hence {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{abs\|''w''}}/2<sup>''i'' + 1</sup>}} {{nowrap\|{{=}} {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>}}}}.		In case 1, by the preceding lemma {{nowrap\|{{abs\|''u''}}<sub>'''i'''</sub> {{=}} {{abs\|''u''}}/2<sup>''i'' + 1</sup>}} and {{nowrap\|{{abs\|''v''}}<sub>'''i'''</sub> {{=}} {{abs\|''v''}}/2<sup>''i'' + 1</sup>}}, and hence {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{abs\|''w''}}/2<sup>''i'' + 1</sup>}} {{nowrap\|{{=}} {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>\|1.75}}}}.

	In case 2, suppose {{nowrap\|''w'' {{=}} ''ustv''}} where ''st'' is as in case 1 and {{abs\|''u''}} and {{abs\|''v''}} are less than {{nowrap\|2<sup>''i'' + 1</sup>}}. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''<sub>''i''</sub>. Using {{nowrap\|{{abs\|''st''}} {{=}} {{abs\|''st''}}<sub>'''i'''</sub>2<sup>''i'' + 1</sup>}}, we have		In case 2, suppose {{nowrap\|''w'' {{=}} ''ustv''}} where ''st'' is as in case 1 and {{abs\|''u''}} and {{abs\|''v''}} are less than {{nowrap\|2<sup>''i'' + 1</sup>}}. Neither ''u'' nor ''v'' can contain an '''i''', as they are subwords of ''F''<sub>''i''</sub>. Using {{nowrap\|{{abs\|''st''}} {{=}} {{abs\|''st''}}<sub>'''i'''</sub>2<sup>''i'' + 1</sup>}}, we have
Line 60:		Line 60:
	thus		thus

	{{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> ≥ {{abs\|''st''}}<sub>'''i'''</sub>}} {{nowrap\|{{=}} {{abs\|''st''}}/2<sup>''i'' + 1</sup>}} {{nowrap\|{{=}} {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>}} − 1}}.		{{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> ≥ {{abs\|''st''}}<sub>'''i'''</sub>}} {{nowrap\|{{=}} {{abs\|''st''}}/2<sup>''i'' + 1</sup>}} {{nowrap\|{{=}} {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>\|1.75}} − 1}}.

	On the other hand, {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> < {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>}}}}, lest ''u'' or ''v'' have an '''i'''. Therefore {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>}} − 1}}.		On the other hand, {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> < {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>\|1.75}}}}, lest ''u'' or ''v'' have an '''i'''. Therefore {{nowrap\|{{abs\|''w''}}<sub>'''i'''</sub> {{=}} {{ceil\|{{abs\|''w''}}/2<sup>''i'' + 1</sup>\|1.75}} − 1}}.
	}}		}}