2
$\begingroup$

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.

$\endgroup$
2
2
+50
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.