On the Multi-Interval Ulam-Rényi Game: for 3 lies 4 intervals suffice

Abstract

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=\Theta (e).$ This linearity conjecture is supported by the known results for small values of $e$. For $e\le 2$ we have $k_e=e.$ 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.$

31 pages, 5 figures, extension of the result to non-asymptotic strategies