On the Multi-Interval Ulam-R\'enyi Game: for 3 lies 4 intervals suffice

We study the problem of identifying an initially unknown $m$-bit number by using yes-no questions when up to a fixed number $e$ of the answers can be erroneous. In the variant we consider here questions are restricted to be the union of up to a fixed number of intervals. For any $e\ge 1$ let $k_e$ be the minimum $k$ such that for all sufficiently large $m$, there exists a strategy matching the information theoretic lower bound and only using $k$-interval questions. It is known that $k_e=O(e^2)$. However, it has been conjectured that the $k_e=\mathrm{\Theta }(e)\mathrm{.}$ This linearity conjecture is supported by the known results for small values of $e$. For $e\le 2$ we have $k_e=e\mathrm{.}$ We extend these results to the case $e=3$. We show $k_3\le 4$ improving upon the previously known bound $k_3\le 10.$