We study the problem of identifying an initially unknown m-bit number by using yes-no questions when up to a xed 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 xed number of intervals. For any e 1 let ke be the minimum k such that for all su ciently large m, there exists a strategy matching the information theoretic lower bound and only using k-interval questions. It is known that ke = O(e2). However, it has been conjectured that the ke = (e): This linearity conjecture is supported by the known results for small values of e. For e 2 we have ke = e: We extend these results to the case e = 3. We show k3 4 improving upon the previously known bound k3 10: In the Ulam-Renyi game with multi-interval questions, two players, called Questioner and Responder|for reasons which will become immediately clear| x three integer parameters: m 0; e 0 and k 1: Then, Responder chooses a number x from the set U = f0; 1; : : : ; 2m 1g; and keeps it secreto to Questioner. The task of Questioner is to identify the secret number x chosen by Responder asking k-interval queries. These are yes-no membership questions of the type \Does x belong to Q?" where Q is any subset of the search space which can be expressed as the union of k intervals. We identify a question with the subset Q: Therefore, the set of allowed questions is given by the family of sets:
Introduction T = ( k [ fai; ai + 1; : : : ; big j 0 i=1 a1 b1 a2 b2 ak bk < 2m ) Questioner's questions can refer to any subset, without the restriction to kinterval queries. A fortiori, the lower bound holds for the multi-interval game for any value of k. Strategies of size Nmin(2m; e); i.e., matching the information theoretic lower bound, are called perfect.
It is known that for any e 0 and up to nitely many exceptional values of m; Questioner can infallibly discover Responder's secret number asking Nmin(2m; e) questions. However, in general such perfect strategies rely on the availability of arbitrary subset questions, i.e., any subset of the search space [20].
When the cardinality of the search space is 2m the description of an arbitrary subset query requires 2m bits. Moreover, in order to implement the known strategies using Nmin(2m; e) queries, (e2m) bits are necessary to record the intermediate states of the game (see the next section for the details). In contrast, a k-interval-query can be expressed by simply providing the boundaries of the k-intervals de ning the question, hence reducing the space requirements of the strategy to only 2k m bits.
On the basis of these considerations, we will focus on the following problem: Main question. For given e 0, denote by ke the smallest integer k such that for all su ciently large m Questioner has a perfect strategy in the multi-interval game over the set of m-bit numbers only using k-interval queries. What is the value of ke for e = 1; 2; : : : ?
In [14] it was proved that for e = 2 for any m 0 (up to nitely many exceptions) there exists a searching strategy for Questioner of size Nmin(m; e) (hence perfect) only using 2-interval questions, and, conversely, perfect strategies which only use 1-interval questions cannot generally exist. The case e = 1 is analysed in [6] where it is shown that perfect strategies exists for e = 1 even when only using 1-interval questions. However, comparison questions|of the type \Is x q?"|are not powerful enough to provide perfect strategies for the case e = 1 [19, 2].
These results show that for e 2; the answer to our main question is ke = e: In [6] one of the authors proved that for any e 1 there exists k = O(e2) such that for all su ciently large m Questioner can identify an m-bit number by using exactly N (2m; e) k-interval questions when Responder can lie at most e times. In [6] also conjectured that ke = O(e) interval might su ce for any e and all su ciently large m. We will refer to this as the linearity conjecture. Our result. We focus on the case e = 3. We show that for any su ciently large m, there exists a strategy to identify an initially unknown m-bit number when up to 3 answers are lies, which matches the information theoretic lower bound and only uses 4-interval queries. With respect to the main question above, we are showing here that k3 4: This way we signi cantly improve the best previously known bound of [6] yielding k3 10: We note that the main tool we employ in the analysis (Lemma 2) naturally lends itself to a generalization to any xed e: Ongoing research is about a stronger form of Theorem 1 that together with such a generalized version of Lemma 2 might lead to the proof of the linearity conjecture mentioned above, i.e., ke = O(e): Because of space constraints some proofs are omitted. The complete version can be found at arXiv:1708.08738 [math.CO] Related work. The Ulam-Renyi game [21, 18] has been extensively studied in various contexts including error correction codes [1, 3, 10, 7], learning [4, 9, 16], many-valued logics [8, 10], wireless networks [13], psychophysics [12], and, principally, sorting and searching in the presence of errors (for the large literature on this topic, and the several variants studied, we refer the reader to the survey papers [8, 17] and the book [5]). 2
Basic facts From now on we concentrate on the case e = 3 and the 4-interval questions. Let Q be the subset de ning the question asked by Questioner. Let Q be the complement of Q; i.e., Q = f0; 1; : : : ; 2m 1g n Q:
If Responder answers yes to question Q, then we say that any number y 2 Q satis es the answer and any y 2 Q falsi es the answer. If Responder answers no to question Q, then we say that any number y 2 Q satis es the answer and any y 2 Q falsi es the answer.
For each y 2 U , we de ne (y) as the number of answers falsi ed by y,
truncated at 4: For each i = 0; 1; : : : ; 3; we will also write 1(i) to denote the
set of numbers falsifying exactly i of Responder's answers. And de ne 1(
States and supports. A state is a map : U ! f0; 1; 2; 3; 4g. The type of is the quadruple ( ) = (t0; t1; t2; t3) where ti = j 1(i)j for each i = 0; 1; 2; 3: The support of is the set of all y 2 U such that (y) < 4: A state is nal i its support has cardinality at most one. The initial state is the function mapping each element of U to 0: We formalise the dynamics of states as follows: Answers and resulting states. Let be the current state with support and Q be the new question asked by Questioner. Let b 2 fyes; nog be the answer of Responder. De ne the answer function b : ! f0; 1g associated to question Q by stipulating that b(y) = 0 if and only if y satis es answer b to question Q. Then, the resulting state b is given by b(y) = maxf (y) + b(y); 4g: More generally, starting from state after questions Q1; : : : ; Qt with answers t b1; : : : ; bt the resulting state is b1 b2 bt = maxf (y) + X bj (y); 4g: j=1
In particular, for being the initial state we have that the resulting state after t questions is the truncated sum of the corresponding answer functions associated to Responder's answers.
Strategies. A strategy of size q is a complete binary tree of depth q where each internal node maps to a question Q : The left and right branch stemming out of map to the function answers yes and no associated to question Q : Each leaf ` is associated to the state ` resulting from the sequence of questions and answers associated to the nodes and branches on unique path from the roof to `. In particular, if b1; : : : ; bq are the answers/branches leading to ` then we have ` = b1 bq as de ned above.
The strategy is winning i for all leaves ` we have that ` is a nal state.
We can also extend the above de nition to an arbitrary starting state. Given a state , we say that a strategy S of size q is winning for if for any root to leaf path in S with associated answers b1; : : : ; bq the state b1 bq is nal .
We de ne the character of a state as ch( ) = minfq j wq( ) 2qg; where wq( ) = Pj3=0 j 1(j)j P`3=0j q` is referred to as the qth volume of :
We have that the lower bound Nmin(2m; e); mentioned in the introduction, coincides with the character of the initial state ; such that 1(0) = U and 1(i) = ; for i = 1; 2; 3; 4 (see Proposition 1 below). Notice also that a state has character 0 if and only if it is a nal state.
For a state and a question Q let yes and no be the resulting states according to whether Responder answers, respectively, yes or no, to question Q in state . Then, from the de nition of the qth volume of a state, it follows that for each q 1; we have wq( ) = wq 1( yes) + wq 1( no): A simple induction argument gives the following lower bound [3].
Proposition 1. Let be the state of the game. For any integers 0 q < ch( ) and k 1; starting from state ; Questioner cannot determine Responder's secret number asking only q many k-interval-queries.
In order to nish the search within Nmin(2m; e) queries, Questioner has to guarantee that each question asked induces a strict decrease of the character of the state of the game. The following lemma provides a su cient condition for obtaining such a strict decrease of the character.
wq 1( no)j
If jwq 1( yes) Lemma 1. Let be the current state, with q = ch( ): Let D be Questioner's question and yes and no be the resulting states according to whether Responder answers, respectively, yes or no, to question D:
1 then ch( yes) q 1 and ch( no) q 1: A question which satis es the hypothesis of Lemma 1 will be called balanced. A special case of balanced question is obtained when for a state the question D satis es jD \ 1(i)j = j 1(i)j=2 for each i = 0; : : : ; e: In this case, we also call the question an even splitting.
Intervals and 4-interval-question. An interval in U is either the empty set ; or a set of consecutive elements [a; b] = fx 2 U ja x bg: The elements a; b are called the boundaries of the interval.
A 4-interval question (or simply a question) is any subset Q of U such that Q = I1 [ I2 [ I3 [ I4 where for j = 1; 2; 3; 4; Ij is an interval in U .
The type of Q, denoted by jQj, is the quadruple jQj = [a0Q; a1Q; a2Q; a3Q] where for each i = 0; 1; 2; 3 , aiQ = jQ \ 1(i)j:
Following [14] we visualize the search space as a necklace and restrict it to the set of number which are candidate to be the secret number, i.e., we identify U with its support = U \ Si3=0 1(i):
For any non- nal state, i.e., j Si3=0 1(i)j > 1, for each x 2 Si3=0 1(i) we de ne the successor of x to be the number x + r mod 2m for the smallest 0 < r < 2m such that x + r mod 2m 2 Si3=0 1(i): In particular, for the initial state 0 is the successor of 2m 1:
For a; b 2 Si3=0 1(i) we say that there is an arc from a to b and denote it by ha; bi if the following two conditions hold: (i) (x) = (a) for each element x encountered when moving from a to b in U passing from one element to its successor; (ii) (c) 6= (a) and (d) 6= (b) where a is the successor of c and d is the successor of b. We say that arc ha; bi is on level (a) and call a and b the left and right boundary of the arc.
In words, an arc is a maximal sequence of consecutive elements lying on the same level of the state .
For the sake of de niteness, we allow an arc to be empty. Therefore, we can associate to a state a smallest sequence L of (possibly empty) arcs a0; : : : ; ar 1 such that for each i the levels of arcs ai and ai+1 di er exactly by 1. Note that, by requiring that the length r be minimum the sequence L is uniquely determined up to circular permutation.
For each i = 0; 1; : : : ; r; we say that arcs ai and a(i+1) mod r are adjacent (or neighbours). We say that ai is a saddle if both adjacent arcs are on a lower level, i.e., a(i 1) mod r; a(i+1) mod r 2 1(k 1) and ai 2 1(k) for some k
We say that ai is a mode if both adjacent arcs are on a higher level, i.e., a(i 1) mod r; a(i+1) mod r 2 1(k + 1) and ai 2 1(k) for some k
We say that ai is a step if for some k ai 2 1(k) and either a(i 1) mod r 2 1(k 1); a(i+1) mod r 2 1(k + 1) or a(i 1) mod r 2 1(k + 1); a(i+1) mod r 2 1(k 1).
Based on the above notions, we now de ne a well-shaped state for e lies. De nition 1. Let be a state and L be its associated list of arcs. Then, well shaped i the following conditions hold: is { for i = 0; : : : ; e 1, in L there are exactly (2i + 1) arcs lying on level i. { in L there are exactly e arcs lying on level e.
It is not hard to see that for the case e = 3 under investigation, the only
two feasible well-shaped states are described as follow: 1(0) is an arc S in
; 1(
Starting with S and scanning U with positive orientation, we can list the
twelve arcs (restricted to ) in one of the following two possibilities:
1 = L2N 1S0O1M 2Q3B2H1C2R3A2P 3
2 = L2N 1S0O1B2H1C2Q3M 2R3A2P 3
(
Typical well-shaped states of type (
Let be a state and ha; bi be a non-empty arc of :
We say that a question Q splits the arc ha; bi if there exists an interval I in Q that intersects ha; bi and contains exactly one of its boundaries a; b. In words, there is an interval in the question such that some non-empty part of the arc satis es a yes answer and some non-empty part of the arc satis es a no answer.
If a question Q splits exactly one arc on level i of according to whether such an arc is a mode, a saddle, or a step, we say that at level i the question Q (or, equivalently, an interval of Q) is mode-splitting, saddle-splitting, step-splitting, respectively.
Let Q be a step-splitting question at level i. Let ha; bi be the arc at level i which is split by an interval I of Q. Then, by de nition I contains exactly one of the boundaries of the arc. If I contains the boundary of the arc that anks an arc at level i + 1 we say that Q (or, equivalently, an interval of Q) is downward step-splitting; if I contains the boundary of the arc that anks an arc at level i 1 we say that Q (or, equivalently, an interval of Q) is upward step-splitting.
We say that a question Q covers entirely the arc ha; bi if [a; b] is contained in one of the intervals de ning Q.
If a question Q covers entirely an arc on level i of according to whether such an arc is a mode, a saddle, a step, we say that at level i the the question Q (or, equivalently, an interval of Q) is mode-covering, saddle-covering, step covering, respectively.
Refer to Figure 3 for a pictorial representation of the interval types and questions e ect on states.
We will be interested in having questions that guarantee that both the two possible states resulting from the answer yes and no are well-shaped. We will de ne conditions on the intersection between the intervals de ning the question and the arcs of a (well-shaped) state such that the both yes and no are well shaped. It turns out that this condition can be de ned locally, level by level and arc by arc.
Lemma 2. Given a well-shaped state and a question Q, if the following conditions are satis ed then both yes and no are well-shaped. For each i = 0; 1; 2 (a) At most one arc is splitted on level i (b) Exactly one of the following holds (i) at level i the question Q is mode-splitting; (ii) at level i the question Q is upward step-splitting and mode-covering. (iii) at level i the question Q is downward step-splitting and a mode is completely uncovered|equivalently the complementary question Q is modecovering at level i. (iv) at level i the question Q is saddle-splitting and mode-covering and there is also a mode completely uncovered|equivalently the complementary question Q is mode-covering at level i. (c) If besides the condition in (b) the question Q is also saddle-covering then Q also covers a mode di erent from the one possibly used to satisfy (b). 3
A key result on the existence of 4-interval questions The strategy we propose is based on the approach of Spencer [20]. We are going to recall the strategy presented in [20] and prove how to implement questions in that strategy by means of 4-interval questions. The main technical tool will be to show that we can de ne 4-interval balanced questions and also guarantee that each intermediate state is well-shaped.
In this section, we will characterise questions in terms of the ratio between the components of the question and the components of the state they are applied. We will show conditions for the existence of questions that can be implemented using only 4-intervals and such that the resulting states are well-shaped whenever the state they are applied to is well shaped.
For each of them, we show how to select the exact amount of elements in the query among the arcs representing the state. Then, we prove that no other cases are allowed and nally we show that the well shapeness property of the state is preserved in both states resulting from the answer to the query.
Theorem 1. Let be a well-shaped state of type ( ) = (a0; b0; c0; d0). Let a; b; c; d be integers such that: 0 a
Then there exists a 4-interval question Q of type jQj = [a; b; c; d] that we can ask in state and such that both the resulting "yes" and "no" states are well-shaped.
Proof. We rst show how to select the intervals of the question Q in order to satisfy the desired type. We proceed level by level. For each i = 0; 1; 2; 3; we show how to select up to 4 intervals that cover the required number of elements in the rst i levels. For each level i = 0; 1; 2; 3 we record in a set E(i) the extremes of the intervals selected so far that have a neighbour on the next level. We refer to the elements in E(i) as the boundaries at level i. When processing the next level, we try to select arc neighbouring the elements in E(i) since this means we can cover elements at the new level without using additional intervals. Arguing with respect to such boundaries, we show that the (sub)intervals selected at all level can be merged into at most 4 intervals. Hence the resulting question Q is a 4-interval question. Finally, we will show that asking Q in both the resulting states are well-shaped states.
Recall the arc notation used in (
Moreover, we denote by s+ the boundary between S and A(
Analogously, we denote by h+ the boundary between H and A(
We denote by a+ the boundary between A and A(
Level 0 For any 0 < a a0 there exists s 2 S such that denoting by S the sub-arc of S between s and s+ we have that jS j = a and the boundary of S includes s+: Then we have E (0) fs+g: Therefore, with one interval I(0) = S we can accommodate the a elements on level 0 and guarantee that this interval has an extreme at s+:
Moreover, the interval I(0) on arc S is a mode-splitting interval.
Level 1 By the assumption b d 21 b0e, and the de nition of A(
Therefore the choice of the intervals so far satis es conditions in Lemma 2.
Level 2 Again we argue by cases
(a) c jAj: Then, there exists a in A such that letting A be the sub-arc
of A between a and a+ we have jA j = c and we can cover it with one
interval I(
Then, by the assumption c d c20 e it follows that jAj + jA(
Therefore, there exists e 2 E such that letting E be the sub-arc of E
between e and e+ we have jAj + jA(
Summarising, we can cover the a elements on level 0 and the b elements
on level 1 and the c elements of level 2 with at most four intervals. More
precisely, if, proceeding as above we only use three intervals, I(0); I(
In all the above ve cases, the (partial) question built so far, with the intervals de ned for levels 0, 1, 2, satisfy the conditions of Lemma 2.
Level 3 Let us denote by W; U the two arcs at level 3 which are di erent from
A(
We have two sub-cases:
{ I(
Since the way intervals are extended on level 3 do not a ect the arc covering and splitting on the previous level, we have that in all cases the resulting 4interval question satis es the conditions of Lemma 2, which guarantees that both resulting states are well-shaped. The proof is complete.
Refer to Figures 1 and 2 for a pictorial representation of the 4-intervals question construction in the proof of Theorem 1. 4
The structure of perfect 4-interval strategies for 3 lies We now show how to employ the result of the previous section to obtain a perfect strategy for the Ulam-Renyi game with 3 lies, only using 4-interval questions. We show that, for e = 3, by only relying on 4-interval questions, we can implement the strategy of [20], that can be summarised as follows:
[0; 0; 0; a3Q]. 1. As long as the state satis es Pi2=0 j 1(i)j > 1 ask a question Q of type [a0Q; a1Q; a2Q; a3Q] where, for i = 0; 1; 2; aiQ 2 nb j 21(i)j c; d j 21(i)j eo with the choice of whether to choose oor or ceiling alternating among those levels where j 1(i)j is odd. The value of a3Q is computed based on the choices of a0Q; a1 ; a2Q, in order to guarantee that the resulting question is balanced, i.e.,
Q a3Q = b 12 Pj2=0(j 1(j)j 2ajQ) qj c, where q + 1 is the character of ; 2. when the state satis es Pi2=0 j 1(i)j 1, ask a balanced question Q of type
The condition in 2. can be easily guaranteed. In fact, the following proposition shows that questions in point 2. are implementable by 4-interval questions, preserving the well-shape of the state.
Proposition 2. Let be a well-shaped state with 1(
The main point in the argument of [20] is that, up to nitely many exceptions,
for all m = log jU j, the value a3Q de ned in 1. is feasible, in the sense that using
the above rules yields 0 a3Q j (
We can now employ Theorem 1 to show that the above strategy can be
implemented by a 4-intervals-question. Let Q be the question de ned in 1: Let Q be
the complementary question, and [a0Q; a1Q; a2Q; a3Q] denote its type. For i = 0; 1; 2;
we have aiQ; aiQ d j 21(i)j e: Moreover, we have minfa3Q; a3Qg d 32 j 1(
We can summarise our discussion in the following theorem.
Theorem 2. For all su ciently large m in the game played over the search space f0; : : : ; 2m 1g with 3 lies, there exists a perfect 4-intervals strategy. In particular, the strategy uses at most Nmin(2m; 3) questions and all the states of the game are well shaped, hence representable by exactly 12 log m bits (12 numbers from U ).
Figures L
S
0 1 2 3
L
N
O
H
B
S yes
I(
C
M
Q
I(
R 0 1 2 3
C