Friedman's long finite sequences-an unclear step in the proof

80 Views Asked by At

I would like to understand here on page $11$ in the proof of LEMMA $3.2.$ why

sinc $k<b/3$ the only block of $b$ consecutive $3$'s are $b_{q+1}$ and (perhaps) $3^s$

I.e. how $k<b/3$ has been used there ? I'm skipping to $11$ page of a (moderately) technical paper since I'm reading it carefully as it is interesting with the hope that someone else find it interesting too to read it up to that point.

1

There are 1 best solutions below

8
On BEST ANSWER

What is really being used, so far as I can see, is that $k<b$. We know that $yB_pC_pB_{p+1}z$ contains two blocks of $b$ consecutive $3$s, one in $B_p$ and one in $B_{p+1}$, so $3^rC_qB_{q+1}C_{q+1}3^sw$ must also contain two such blocks. $B_{q+1}$ contains one of them. From the top of page $10$ we know that each of $C_q$ and $C_{q+1}$ contains exactly $k$ $3$s, and $k<b$, so neither $C_q$ nor $C_{q+1}$ contains a block of $b$ consecutive $3$s. Thus, the only possible locations for the other block are $3^r$ and $3^s$. However, clause (i) of the definition of type $2$ sequences requires that $r<b$, so $3^s$ is actually the only possible place of the other block of $b$ consecutive $3$s, and therefore we must have $s=b$, matching $B_{p+1}$. This implies that $B_p=B_{q+1}$ and hence that $p=q+1$, and also that $y=3^rC_q=3^rC_{p-1}$. Finally, $y$ is a tail of $C_{p-1}$, so we must have $r=0$, but then $y=C_{p-1}$, contradicting the requirement in the definition of type $1$ subsequence that it be a proper tail of $C_{p-1}$.