For a real number $\lambda > 100$, let $f(\lambda)$ denote the smallest positive integer $k$ satisfying the following property.
For any integer sequence $0<a_1<a_2<…$, if $a_n\leq \lambda n$ holds for infinitely many $n$, then there exist infinitely many pairs $i<j$ such that $S_2(a_j-a_i)=k$.
Show the existence of $f(\lambda)$, and prove that$$\log_{2} \lambda-1<f(\lambda)<2\log_{2} \lambda.$$Here $S_2(m)$ denote the sum of digit in $m$'s binary representation.
Any help would be highly appreciated.
Best Answer
We can show even better upper bound $f(\lambda)\le \log_2(\lambda+1)$ as follows. Let $\varepsilon>0$ be any number. We claim that a set $N_\varepsilon=\{n\in\Bbb N: a_{n+1}<a_n+\lambda+\varepsilon \}$ is infinite. Indeed, suppose to the contrary that for some $\varepsilon>0$ the set $N_\varepsilon$ is finite. Put $N=\max N_\varepsilon$. Then for each $n>N$ we have $a_n\ge a_{N}+(n-N)(\lambda+\varepsilon)$, which contradicts to inequality $a_n\le \lambda n$ for all sufficiently large $n$.
Clearly, that $m\ge 2^{S_2(m)}-1$ for each natural $m$, that is $S_2(m)\le \log_2 (m+1)$. Since for each $i\in N_\varepsilon$ we have $ a_{i+1}-a_i< \lambda+\varepsilon$, it follows $f(\lambda)<\log_2(\lambda+\varepsilon+1)$, that is $f(\lambda)\le \log_2(\lambda+1)$.