Reading Eight Erdős Problems Together

Why a small allowance along a subsequence is insufficient

Without eventual congruences, the allowance $F(n)=n-1$ for $n\ge 2$ gives the full interval $[0,1]$, whereas $F(n)=o(n)$ as $n\to \mathrm{\infty }$ gives a null attainable set. The latter conclusion does not follow from small allowances merely along a subsequence, as the example below shows.

For the nullity assertion, eventually $F(n)+1\le n/2$ and $F(n)\le n$. Thus the number of prefixes through $N$ is at most $C{2}^{-N}N!$ for a fixed $C$, while the capacity after $N$ is at most $\sum _{n>N}n/n!\le 2/N!$. The covering bound of Theorem 6.1(i), allowing zero-capacity levels to be omitted, tends to zero.

For the subsequence counterexample put $F(2k)=0$ and $F(2k+1)=(2k)(2k+1)-1$ for $k\ge 1$, with $F(1)=0$. Then

The total capacity is $1$, and the capacity after each permitted index $2k+1$ is exactly $1/(2k+1)!$, equal to the spacing between its choices. The interval criterion therefore gives every value in $[0,1]$, even though $F(n)/n=0$ at every even index. The exact telescoping identities and sample greedy expansions are reproduced by the script cited in Section 9; the interval conclusion follows from this argument, not from the samples.