Precise coding with noiseless feedback

by

David Lawrence desJardins

S.B. (Massachusetts Institute of Technology), 1983

A dissertation submitted in partial satisfaction of the

requirements for the degree of

Doctor of Philosophy

in Mathematics

in the

GRADUATE DIVISION

of the

UNIVERSITY of CALIFORNIA at BERKELEY

Committee in charge: Professor Elwyn Berlekamp, Chair

Professor David Eisenbud Professor Christos Papadimitriou

Fall 2001 The dissertation of David Lawrence desJardins is approved:

Chair Date \overline{Date} \overline{Date}

University of California at Berkeley Fall 2001

Abstract

Precise coding with noiseless feedback

by

David Lawrence desJardins Doctor of Philosophy in Mathematics

University of California at Berkeley

Professor Elwyn Berlekamp, Chair

The construction of block codes for communicating over discrete, noisy channels is a central problem of information theory. A block code is a collection of codewords with the property that if the sender chooses one of the codewords to transmit, and no more than a specified number of errors occur, then the recipient can with certainty determine which of the codewords was sent.

If the recipient is also able to transmit information to the sender, instantly and without error, then the theoretical information capacity of the forward channel is not increased, but our ability to utilize that capacity with a coding scheme is enhanced. Assume a binary forward channel. The reverse channel can be used to transmit to the sender, after each bit is sent, the value of the bit as received by the recipient. The sender can then use that information in deciding what bit to send next. By an adaptive block code, we mean a mapping from codewords to labeled binary trees: for each codeword, we send a sequence of bits, where each bit sent may depend not only on the codeword but on all of the received values of the previous bits. We require that the recipient be able to determine which codeword was chosen, so long as no more than a specified number of errors occur.

We demonstrate that for many choices of parameters, adaptive block codes may be constructed that are much better than standard block codes that do not assume the possibility of feedback. For a wide range of parameters, we construct precisely optimal adaptive block codes, which contain the maximum possible number of codewords, given the length of the codes and the number of errors they tolerate.

The construction of adaptive block codes is equivalent to the formulation of strategies for a game described by Ulam, a version of “Twenty Questions” with lies. Our results resolve Ulam’s open question about that game: given 10^{6} objects, how many binary questions are required to identify a particular object, when the answerer is permitted to lie a fixed number of times?

Professor Elwyn Berlekamp Dissertation Committee Chair

Contents

List of Figures v

1 Introduction and preliminaries 1 1.1 Block codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Adaptive block codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Ulam’s game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4 State-space formulation . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.5 Volume bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.6 Borderline states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.7 Doublets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.8 Zero-error states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.9 Dominated states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.10 Translation bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.11 Infinite state sequences . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.12 Fibonacci states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Computational methods 19 2.1 Summation rule for states . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Summation rule for state sequences . . . . . . . . . . . . . . . . . . . 21 2.3 Game trees for states . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.4 Game trees for state sequences . . . . . . . . . . . . . . . . . . . . . . 23 2.5 Truncated state sequences . . . . . . . . . . . . . . . . . . . . . . . . 24 2.6 Losing states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.7 A three-step losing state . . . . . . . . . . . . . . . . . . . . . . . . . 28

3 Optimal codes 30 3.1 Main Result . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 3.2 Upper bounds on M . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.3 Search algorithm for states . . . . . . . . . . . . . . . . . . . . . . . . 33 3.4 Partitioning algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 34 3.5 Summation algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.6 Lifting game trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 3.7 Computational Results . . . . . . . . . . . . . . . . . . . . . . . . . . 37

A Program Listing 39 B Program Output 52 Bibliography 64

v

List of Figures Chapter 1

Introduction and preliminaries

1.1 Block codes

Consider the problem of transmitting a message through a noisy channel. We will generally restrict our attention to the symmetric binary channel: the sender transmits one bit at a time, an element of {0, 1}, and the receiver receives that bit with probability 1 − g, or the complementary bit with probability g, where g is in the interval (0, 1/2). When the received bit differs from the transmitted bit, this is considered an error.

If N > 0 bits are transmitted through the binary symmetric channel, it is possible (albeit unlikely) that all of the bits are received in error. In order to make a deterministic analysis possible, coding theorists frequently consider the case where it is assumed that no more than E errors occur, for some E between 0 and N. If we fix an error-correction fraction f > g, then for sufficiently large N, we can say almost surely that the number of errors E will be less than fN. So schemes that correct a fixed number of errors are useful in practice.

A central problem of coding theory is the following: given that N bits are transmitted, and no more than E errors occur, what is the maximum number of distinct messages M that may be sent without any possibility of error on the part of the recipient? A construction that permits this is called a block code, the integer N is called the length of the code, and the integer E is called the error-correction capacity.

Definition 1 (Hamming weight). H(x_{1}, …, x_{K}) is the number of the x_{i} that are nonzero.

Definition 2 (Block code). A block code of length N and error-correcting capacity E is a sequence of functions

t_{I} : {1, 2, …, M} → {0, 1},

for I = 1, 2, …, N, with the following equivalent properties:

• For any m ≠ m′, there are at least 2E + 1 values of I such that t_{I}(m) ≠ t_{I}(m′).

• For any m ≠ m′, and any binary tuples (e_{1}, …, e_{N}) and (e′_{1}, …, e′_{N}) with H(e_{1}, …, e_{N}) ≤ E and H(e′_{1}, …, e′_{N}) ≤ E, there must be some I such that t_{I}(m) ⊕ e_{I} is not equal to t_{I}(m′) ⊕ e′_{I}.

Definition 3 (Rate). The rate of a block code is

R = (lg M)/N.

Definition 4 (Error-correction fraction). The error-correction fraction of a block code is

f = E/N.

To use the block code to transmit a message m, we send the sequence of bits

(t_{1}(m), …, t_{N}(m)).

If an error pattern (e_{1}, …, e_{N}) occurs, the receiver receives the tuple

(t_{1}(m) ⊕ e_{1}, …, t_{N}(m) ⊕ e_{N}).

Under the hypothesis that H(e_{1}, …, e_{N}) ≤ E, there is no other message m′ and error pattern (e′_{1}, …, e′_{N}) with H(e′_{1}, …, e′_{N}) ≤ E that would cause the same tuple to be received. So the receiver can uniquely identify the message m, and the error pattern (e_{1}, …, e_{N}).

1.2 Adaptive block codes

We are concerned with a variation of the above problem. Assume that after each bit is transmitted, the receiver has the opportunity to transmit an unlimited amount of information, instantly and without the possibility of error, to the sender. We can easily conclude that the receiver cannot gain any advantage by sending any more information than a single bit per received bit: the value of the received bit. This is the only information that the receiver has and the sender does not.

Shannon (1956) showed that this feedback cannot increase the theoretical capacity of the forward channel. Nevertheless, as we shall see, the feedback does prove useful at code rates below capacity. It can be used for more explicit encoding and decoding strategies, and at sufficiently low rates, can significantly improve the error-correction capability.

An adaptive block code has the same parameters N, E, and M as a standard block code, defined above. The sender agrees in advance with the receiver on a communication scheme. The sender then is given one of M messages to send. Based on that choice, the sender then transmits bits, one at a time. After each bit is sent, the sender learns whether an error occurred in sending that bit, and can use that information in deciding what bit to send next. After N bits are sent, the receiver must be able to determine which one of the M messages was chosen, under the assumption that no more than E errors occurred.

Definition 5 (Adaptive block code). An adaptive block code of length N and error-correcting capacity E is a sequence of functions

t_{I} : {1, 2, …, M} × {0, 1}^{I−1} → {0, 1}

for I = 1, 2, …, N. The functions t_{I} must have the property:

• For any m ≠ m′ and any binary tuples (e_{1}, …, e_{N}) and (e′_{1}, …, e′_{N}) with H(e_{1}, …, e_{N}) ≤ E and H(e′_{1}, …, e′_{N}) ≤ E, then there must be some I such that t_{I}(m, e_{1}, …, e_{I−1}) ⊕ e_{I} is not equal to t_{I}(m′, e′_{1}, …, e′_{I−1}) ⊕ e′_{I}.

The rate and error-correction fraction are defined as for a block code.

To use the adaptive block code to transmit a message m, we send the sequence of

bits

(t_{1}(m), t_{2}(m, e_{1}), …, t_{N}(m, e_{1}, …, e_{N−1})),

where e_{i} is 1 if an error occurred in transmitting the i-th bit and 0 otherwise. Note

that t_{I}(m) depends only upon information available to the sender, from the feedback

channel, after transmitting the first I − 1 bits. If an error pattern (e_{1}, …, e_{N}) occurs,

the receiver receives the tuple

(t_{1}(m) ⊕ e_{1}, t_{2}(m, e_{1}) ⊕ e_{2}, …, t_{N}(m, e_{1}, …, e_{N−1}) ⊕ e_{N}).

Under the hypothesis that H(e_{1}, …, e_{N}) ≤ E, there is no other message m′ and error

pattern (e′_{1}, …, e′_{N}) with H(e′_{1}, …, e′_{N}) ≤ E that would cause the same tuple to be

received. So the receiver can uniquely identify the message m, and the error pattern

(e_{1}, …, e_{N}).

1.3 Ulam’s game

In his autobiography, Stanislaw Ulam proposes the following game, “a variation

on the game of Twenty Questions”:

Someone thinks of a number between one and one million (which is just less than 2^{20}). Another person is allowed to ask up to twenty questions, to each of which the first person is supposed to answer only yes or no. Obviously the number can be guessed by asking first, “Is the number in the first half million?” then again reduce the reservoir of numbers in the next question by one-half, and so on. Finally the number is obtained in less than log_{2}(1, 000, 000). Now suppose one were allowed to lie once or twice, then how many questions would one need to get the right answer? One clearly needs more than n questions for guessing one of 2^{n} objects because one does not know when the lie was told. This problem is not solved in general.

We can formalize Ulam’s game as follows.

Game 1 (Ulam’s game). Alice secretly chooses a number from {1, 2, …, M}. Bob

then asks questions, one at a time, each of which is a subset of {1, 2, …, M}. Alice answers each question with 1 (the secret number is in the set) or 0 (the secret number is not in the set). Bob is allowed N questions, and Alice is constrained that at most E of her answers may be false. Bob’s goal is a questioning strategy such that, after the N questions, he has uniquely identified the secret number.

It turns out that the existence of winning strategies for Ulam’s game is exactly equivalent to the existence of adaptive block codes.

Theorem 1. Bob has a winning strategy for Ulam’s game with parameters N, E, M if and only if there exists an adaptive block code with the same parameters.

Proof. First, suppose that we are given an adaptive block code; we use this to generate a winning strategy for Ulam’s game. Bob’s first question is the set {m|t_{1}(m) = 1}, to which Bob receives the reply r_{1}. Bob can then compute the function e_{1}(m) = r_{1} ⊕ t_{1}(m), which indicates whether Alice answered the first question falsely under the hypothesis that the secret value is m. Bob’s second question is the set {m|t_{2}(m, e_{1}(m)) = 1}, to which Bob receives the reply r_{2}. Bob can then compute the function e_{2}(m) = r_{2} ⊕ t_{2}(m, e_{1}(m)), which indicates whether Alice answered the second question falsely under the hypothesis that the secret value is m. Bob’s third question is the set {m|t_{3}(m, e_{1}(m), e_{2}(m)) = 1}, and so on.

After N questions, Bob can compute for each m the tuple (e_{1}(m), …, e_{N}(m)). By the constraint that Alice may answer falsely at most E times, we know that for the actual secret m, H(e_{1}(m), …, e_{N}(m)) ≤ E. Suppose that there is some other m′ such that H(e_{1}(m′), …, e_{N}(m′)) ≤ E. Then, by the definition of the adaptive block code, there must be some I such that t_{I}(m, e_{1}(m), …, e_{I−1}(m)) ⊕ e_{I}(m) ≠ t_{I}(m′, e_{1}(m′), …, e_{I−1}(m′)) ⊕ e_{I}(m′). But, by the definition of the function e_{I}, both sides of this inequality are equal to r_{I}.

Second, suppose that we are given a winning strategy for Ulam’s game; we use this to construct an adaptive block code. Let S_{1} be Bob’s first question. We define t_{1}(m) to be 1 if m ∈ S_{1}, 0 otherwise. Let S_{2}(r_{1}) be Bob’s second question, given that the response to the first question was r_{1}. Define t_{2}(m, e_{1}) to be 1 if m ∈ S_{2}(e_{1} ⊕ t_{1}(m)), 0 otherwise. Let S_{3}(r_{1}, r_{2}) be Bob’s third question, given the first two responses. Define t_{3}(m, e_{1}, e_{2}) to be 1 if m ∈ S_{3}(e_{1} ⊕ t_{1}(m), e_{2} ⊕ t_{2}(m, e_{1})), 0 otherwise. And so on.

Consider any m ≠ m′, and (e_{1}, …, e_{N}) and (e′_{1}, …, e′_{N}), with H(e_{1}, …, e_{N}) ≤ E and H(e′_{1}, …, e′_{N}) ≤ E. Suppose that e_{I} ⊕t_{I}(m, e_{1}⊕t_{1}(m), …, e_{I−1}⊕t_{I−1}(m)) equals e′_{I} ⊕ t_{I}(m′, e′_{1} ⊕ t_{1}(m′), …, e′_{I−1} ⊕ t_{I−1}(m′)) for every I = 1, 2, …, N. Then if Alice chooses m as the secret number, and gives false answers for those values of I such that e_{I} = 1, then Bob will ask exactly the same questions and receive exactly the same answers as if Alice chooses m′ as the secret number, and gives false answers for those values of I such that e′_{I} = 1. So, by the assumption that Bob’s questioning strategy is valid, no such m and m′ can exist; this proves that the functions t_{I} form an adaptive block code.

Note that if we modify Ulam’s game so that Alice does not have to fix her secret choice at the beginning of the game, but only must answer all of the questions in such a way that they are consistent with some possible secret, then the question of existence of a winning strategy for Bob is unchanged. If Bob has a strategy that always wins when Alice chooses her secret in advance, then the same strategy must always win even if Alice is not forced to commit to a particular secret at the start.

1.4 State-space formulation

In this section we present another equivalent formulation of the construction of adaptive block codes, or questioning strategies for Ulam’s game. Given integers N, E, and M, we will consider a game played with finite tuples of nonnegative integers. We will delete trailing zeroes from the tuples, so that the (E +1)-tuple (s_{0}, s_{1}, …, s_{E}) is equivalent to the E-tuple (s_{0}, s_{1}, …, s_{E−1}) if s_{E} = 0.

Definition 6 (Translation operator). We define an operator T on tuples of nonnegative integers. (The letter T denotes “translation”.) Given the (E + 1)-tuple s = (s_{0}, s_{1}, …, s_{E}),

Ts = (s_{1}, s_{2}, …, s_{E}, 0) = (s_{1}, s_{2}, …, s_{E}).

Game 2 (Tuple-game). The tuple-game has N rounds, and begins with an (E +1)- tuple of natural numbers, s_{0} ∈ ℕ^{E+1}. First, Bob partitions s_{0} into a_{0}, b_{0} ∈ ℕ^{E+1} such that s_{0} = a_{0} + b_{0}. Then, Alice chooses either Ta_{0} + b_{0} or a_{0} + Tb_{0}, and her choice becomes s_{1}. Then the process is repeated: Bob chooses a_{1}, b_{1} ∈ ℕ^{E+1} such that s_{1} = a_{1} + b_{1}, and Alice chooses either Ta_{1} + b_{1} or a_{1} + Tb_{1} to be s_{2}. And so on. At the end of N rounds, Bob wins the game if the sum of the elements of s_{N} is 0 or 1; Alice wins otherwise.

Theorem 2. Let s_{0} be the (E + 1)-tuple (0, 0, …, 0, M). Bob has a winning strategy for the tuple-game with N rounds and initial state s_{0} if and only if Bob has a winning strategy for Ulam’s game with parameters N, E, M.

Proof. First, suppose that we are given a winning strategy for the tuple-game; we use this to generate a winning strategy for Ulam’s game.

Suppose that I questions S_{1}, S_{2}(r_{1}), …, S_{I}(r_{1}, …, r_{I−1}) have been asked in Ulam’s game, with answers (r_{1}, …, r_{I}). For any m ∈ {1, 2, …, M}, we can compute: e_{1}(m) = r_{1} ⊕ t_{1}(m), where t_{1}(m) is 1 if m ∈ S_{1}, 0 otherwise; e_{2}(m) = r_{2} ⊕ t_{2}(m, e_{1}(m)), where t_{2}(m, e_{1}(m)) is 1 if m ∈ S_{2}(r_{1}), 0 otherwise; and so on to e_{I}(m) = r_{I} ⊕ t_{I}(m, e_{1}(m), …, e_{I−1}(m)), where t_{I}(m, e_{1}(m), …, e_{I−1}(m)) is 1 if m ∈ S_{I}(r_{1}, …, r_{I−1}), 0 otherwise. We can then define E_{I}(m) = E − H(e_{1}(m), …, e_{I}(m)). A winning strategy for Ulam’s game is one which has, for every sequence (r_{1}, …, r_{N}), E_{N}(m) ≥ 0 for at most one value of m.

Given a partial sequence of received bits (r_{1}, …, r_{I}), we can define the state s_{I} ∈ ℕ^{E+1} to be the tuple where the J-th coordinate s_{I}(J) is the size of the set {m|E_{I}(m) = J}, for J = 0, 1, …, E. Note that s_{0} = (0, 0, …, 0, M), as we specified for the tuple-game.

Given a partition of s_{I} into a_{I} + b_{I}, we can choose a partition of {1, 2, …, M} into disjoint subsets A_{I} and B_{I}, such that the size of {m ∈ A|E_{I}(m) = J} is exactly the J coordinate of a_{I}. (For example, we can choose A to contain the smallest a_{I}(J) of the total s_{I}(J) such messages. The elements of {1, 2, …, M} with E_{I}(m) < 0 can go into either A or B.)

Our strategy for the tuple-game gives us such a partition of s_{I} into a_{I} +b_{I}. Choose a set A_{I}, as above; this becomes the question S_{I+1} for Ulam’s game. If the answer r_{I+1} = 1 is received, then E_{I+1}(m) = E_{I}(m) for m ∈ A_{I} and E_{I+1}(m) = E_{I}(m) − 1 for m ∈ B_{I}, which implies that s_{I+1}, defined as above, is equal to a_{I} + Tb_{I}. While, if the answer r_{I+1} = 0 is received, then E_{I+1}(m) = E_{I}(m) − 1 for m ∈ A_{I} and E_{I+1}(m) = E_{I}(m) for m ∈ B_{I}, which implies that s_{I+1}, defined as above, is equal to Ta_{I} + b_{I}. Thus, regardless of whether Alice answers 0 or 1 in Ulam’s game, the new state s_{I+1} corresponds to one of Alice’s possible choices in the tuple-game. So, after N such questions, if our strategy for the tuple-game is successful, the sum of the elements of s_{N} will be zero or one, which means that there is at most one m ∈ {1, 2, …, M} with E_{N}(m) ≥ 0, which means that this was a winning strategy for Ulam’s game.

Second, suppose that we are given a winning strategy for Ulam’s game; we use this to generate a winning strategy for the tuple-game. We can use the (I + 1)-st question S_{I+1}(r_{1}, …, r_{I}) in Ulam’s game to define a partition of the state s_{I} into a_{I} + b_{I}, by letting a_{I}(J) be the number of elements m ∈ S_{I+1} with E_{I}(m) = J. We can then interpret Alice’s choice of Ta_{1} + b_{1} or a_{1} + Tb_{1} in the tuple-game as a choice of r_{I+1} = 0 or 1 respectively in Ulam’s game, use that new state of Ulam’s game to determine a new question for Ulam’s game, and so on. If our strategy for Ulam’s game is successful, then after N questions and answers, we will have at most one m ∈ {1, 2, …, M} with E_{N}(m) ≥ 0, which implies that the state vector s_{N} will sum to zero or one, which is the winning condition for the tuple-game.

Following Berlekamp, we will call such an (E + 1)-tuple a state.

Definition 7 (Winning N-state). The state s is a winning N-state if Bob has a winning strategy for the tuple-game of N rounds with initial state s.

Corollary 1. The following are all equivalent:

• The (E + 1)-tuple (0, 0, …, 0, M) is a winning N-state.

• Bob has a winning strategy for Ulam’s game with parameters N, E, M.

• There exists an adaptive block code with parameters N, E, M.

Proof. Immediate from Theorem 1 and Theorem 2.

Lemma 1. If s is a winning N-state, s is also a winning N′-state for any N′ > N.

Proof. In subsequent rounds of the tuple-game, the sum of the elements of s_{I} is nonincreasing, because the sum of the elements of Ta is at most the sum of the elements of a, and the sum of elements of Tb is at most the sum of the elements of b. So, if Bob has a strategy that forces the sum of the elements of s_{N} to be at most 1, then Bob can force the sum of the elements of s_{N′} to be at most 1, for any N′ > N.

1.5 Volume bound

Definition 8 (Partial sum of state). Given a state s = (s_{0}, s_{1}, …, s_{E}), we define

s^{(J)} = ∑_{J′=J}^{E} s_{J′}.

We also define s^{(J)} = 0 for J > E.

Lemma 2 (Partial sum representation). The mapping

(s_{0}, s_{1}, …, s_{E}) ↔ (s^{(0)}, s^{(1)}, …, s^{(E)})

is a one-to-one correspondence between (E + 1)-tuples of nonnegative integers, and nonincreasing tuples of nonnegative integers.

Proof. If (s_{0}, s_{1}, …, s_{E}) is nonnegative, then s^{(J)} is certainly nonnegative, and s^{(J)} = s^{(J+1)} + s_{J}, so s^{(J)} ≥ s^{(J+1)}. Conversely, if (s^{(0)}, s^{(1)}, …, s^{(E)}) is nonnegative and nonincreasing, then s_{E} = s^{(E)} is nonnegative, and s_{J} = s^{(J)} − s^{(J+1)} is nonnegative for J < E.

Given this lemma, we will use the two representations of a state s interchangeably. The following terminology will be useful:

Definition 9 (Singlet). A state s with s^{(0)} = 1 is called a singlet.

Definition 10 (Doublet). A state s with s^{(0)} = 2 is called a doublet.

By definition, every singlet is a winning 0-state, and thus a winning N-state for every N.

Lemma 3. If s is a winning N-state and s is not a singlet, then s_{J} = 0 for J ≥ N.

Proof. Since s is not a singlet, N is greater than 0. Since s is a winning N-state, s = a + b where Ta + b and a + Tb are winning (N − 1)-states. If Ta + b is a singlet, and a+Tb is a singlet, then a_{J} = b_{J} = 0 for all J > 0. But if either Ta+b or a+Tb is not a singlet, then by induction a_{J} = b_{J} = 0 for J ≥ N, so s_{J} = 0 for J ≥ N.

Following Berlekamp’s terminology, we now define the volume of an N-state:

Definition 11 (Volume).

Vol_{N}(s) = ∑_{J=0}^{E} s_{J} ∑_{J′=0}^{J} \binom{N}{J′} = ∑_{J=0}^{E} s^{(J)}\binom{N}{J}.

When N is not clear from the context, we will refer to Vol_{N} as the N-volume. Note that throughout this text we take \binom{N}{J} = 0 when N < J or J < 0. Given this definition, we can easily prove the following lemma and theorem.

Lemma 4 (Conservation of Volume). If s = a + b, then Vol_{N}(s) = Vol_{N−1}(Ta + b) + Vol_{N−1}(a + Tb).

Proof. Since \binom{N}{J} = \binom{N−1}{J} + \binom{N−1}{J−1}, Vol_{N}(s) = Vol_{N−1}(s) + Vol_{N−1}(Ts) for any state s. So Vol_{N}(s) = Vol_{N}(a + b) = Vol_{N}(a) + Vol_{N}(b) = Vol_{N−1}(a) + Vol_{N−1}(Ta) + Vol_{N−1}(b) + Vol_{N−1}(Tb) = Vol_{N−1}(Ta + b) + Vol_{N−1}(a + Tb).

Theorem 3 (Volume Bound). If s is a winning N-state, then Vol_{N}(s) ≤ 2^{N}.

Proof. If N = 0 then the result is trivial. Otherwise, proceed by induction on N. If s is a winning N-state, then there exist states a, b such that s = a + b and Ta + b, a+Tb are winning (N −1)-states. So, by the induction hypothesis, Vol_{N−1}(Ta+b) ≤ 2^{N−1} and Vol_{N−1}(a + Tb) ≤ 2^{N−1}. But, using conservation of volume, Vol_{N}(s) = Vol_{N−1}(Ta + b) + Vol_{N−1}(a + Tb) ≤ 2^{N−1} + 2^{N−1} = 2^{N}.

1.6 Borderline states

Definition 12 (Borderline winning N-state). A winning N-state s is a borderline winning N-state if Vol_{N}(s) = 2^{N}; that is, if it satisfies the volume bound with equality.

Theorem 4. If s is a borderline winning N-state, and s is not a singlet, then s is not a winning (N − 1)-state.

Proof. Since Vol_{N}(s) = 2^{N} > 0, s_{J} > 0 for some J. By Lemma 3, s_{J} > 0 for some J < N. Thus we compute:

2^{N} = Vol_{N}(s) = ∑_{J=0}^{E} s^{(J)}\binom{N}{J}

= ∑_{J=0}^{E} s^{(J)}\binom{N − 1}{J} + ∑_{J=0}^{E} s^{(J)}\binom{N − 1}{J − 1}

= ∑_{J=0}^{E} s^{(J)}\binom{N − 1}{J} + ∑_{J=0}^{E−1} s^{(J+1)}\binom{N − 1}{J}

= ∑_{J=0}^{E}(2s^{(J)} − s_{J})\binom{N − 1}{J}

= 2 Vol_{N−1}(s) − ∑_{J=0}^{E} s_{J} \binom{N − 1}{J}

< 2 Vol_{N−1}(s)

since the sum on the next to last line is positive. So Vol_{N−1}(s) > 2^{N−1}, so s cannot be a winning (N − 1)-state.

Lemma 5. Given a winning N-state s = (s_{0}, s_{1}, …, s_{E}), there is a borderline winning N-state s′ = (s′_{0}, s_{1}, …, s_{E}) which differs from s only in the 0th coordinate.

Proof. When N = 0 this is clear, because a winning 0-state is either a singlet, in which case it already meets the volume bound with equality, or is zero, in which case s′ = (1) satisfies the conclusion.

Otherwise, proceed by induction on N. Given a winning N-state s, there is a partition s = a + b such that c = Ta + b and d = a + Tb are winning (N − 1)- states. By the induction hypothesis, there are borderline winning (N − 1)-states c′, d′ which differ from c, d respectively only in the 0th coordinate. Let b′ = c′ − Ta, a′ = d′ − Tb, and s′ = a′ + b′. Then s′ − s = (a′ − a) + (b′ − b) = (c′ − c) + (d′ − d), so s′ differs from s only in the 0th coordinate.

But c′, d′ are borderline winning (N − 1)-states, so Vol_{N−1}(c′) = Vol_{N−1}(d′) = 2^{N−1}. By conservation of volume, Vol_{N}(s′) = Vol_{N−1}(c′) + Vol_{N−1}(d′) = 2^{N−1} + 2^{N−1} = 2^{N}. So s′ is a borderline winning N-state.

1.7 Doublets

Theorem 5 (Doublet theorem). If s is a doublet, and

s = (0, 0, …, 0, 1, 0, …, 0) + (0, 0, …, 0, 1, 0, …, 0),

where the 1’s occur in positions J and K, then s is a borderline winning (J + K + 1)- state, and not a winning (J + K)-state.

Proof. By induction. Write s = a + b, where a and b are singlets with a_{J} = b_{K} = 1. Then each of Ta + b and a + Tb is either a singlet, or is a doublet that by induction is a winning (J + K)-state. So s is a winning (J + K + 1)-state.

Let N = J + K + 1. Then

Vol_{N}(s) = ∑_{J′=0}^{J} \binom{N}{J′} + ∑_{J′=0}^{K} \binom{N}{J′}

= ∑_{J′=0}^{J} \binom{N}{J′} + ∑_{J′=0}^{K} \binom{N}{N − J′}

= ∑_{J′=0}^{J} \binom{N}{J′} + ∑_{J′=N−K}^{N} \binom{N}{J′}

= ∑_{J′=0}^{N} \binom{N}{J′}

= 2^{N},

so s is a borderline winning (J + K + 1)-state.

1.8 Zero-error states

The following result corresponds to the trivial strategy for the game of “Twenty Questions”.

Theorem 6 (Twenty questions). If E = 0, so s = (s_{0}), then s is a winning N-state if and only if s_{0} ≤ 2^{N}.

Proof. Vol_{N}(s) = s_{0}, so “only if” follows from the volume bound. For the “if” direction, if N = 0, then s = (1) or s = (0) which are winning 0-states. If N > 0, then we can write s = a+b where a = (a_{0}), b = (b_{0}), and a_{0}, b_{0} ≤ 2^{N−1}. So Ta+b = b and a + Tb = a, and by induction both a and b are winning (N − 1)-states, so s is a winning N-state.

1.9 Dominated states

Definition 13 (Domination). We say that t dominates s if (and only if)

s^{(J)} ≤ t^{(J)} for all J = 0, 1, …, E.

We will use the notation t ≥ s for this relation.

Theorem 7 (Domination theorem). If t dominates s, and t is a winning N-state, then s is a winning N-state.

Proof. By induction on N. The statement is trivial when N = 0. Otherwise, since t is a winning N-state, t = c+d, where Tc+d and c+Td are winning (N −1)-states. And s^{(J)} ≤ t^{(J)} = c^{(J)} + d^{(J)} for each J. If we find a, b such that s = a + b, a ≤ c, and b ≤ d, then we are done, because Ta + b ≤ Tc + d and a + Tb ≤ c + Td, so Ta + b and a + Tb are winning (N − 1)-states by induction.

The tuples (a^{(0)}, …, a^{(E)}) and (b^{(0)}, …, b^{(E)}) must satisfy s^{(J)} = a^{(J)} + b^{(J)} for each J, and the constraint that a^{(J)} ≥ a^{(J+1)} and b^{(J)} ≥ b^{(J+1)} for each J. We will construct such a state a, and the corresponding state b, by choosing a^{(E)}, then a^{(E−1)}, and so on.

For each J = 0, 1, …, E, we need to choose a^{(J)}, and b^{(J)} = s^{(J)} − a^{(J)}, such that all of the following inequalities are simultaneously satisfied:

a^{(J+1)} ≤ a^{(J)} ⟺ a^{(J)} ≥ a^{(J+1)}
b^{(J+1)} ≤ b^{(J)} ⟺ a^{(J)} ≤ s^{(J)} − b^{(J+1)}
a^{(J)} ≤ c^{(J)} ⟺ a^{(J)} ≤ c^{(J)}
b^{(J)} ≤ d^{(J)} ⟺ a^{(J)} ≥ s^{(J)} − d^{(J)}.

(Recall that a^{(E+1)} = b^{(E+1)} = 0 by definition.)

Once a valid choice of a^{(J+1)} has been made, there exists at least one value for a^{(J)} that simultaneously satisfies all of these inequalities, because:

a^{(J+1)} + b^{(J+1)} = s^{(J+1)} ≤ s^{(J)} ⟹ a^{(J+1)} ≤ s^{(J)} − b^{(J+1)}
a^{(J+1)} ≤ c^{(J+1)} ≤ c^{(J)} ⟹ a^{(J+1)} ≤ c^{(J)}
b^{(J+1)} ≤ d^{(J+1)} ≤ d^{(J)} ⟹ s^{(J)} − d^{(J)} ≤ s^{(J)} − b^{(J+1)}
s^{(J)} ≤ t^{(J)} = c^{(J)} + d^{(J)} ⟹ s^{(J)} − d^{(J)} ≤ c^{(J)}.

So the sequence of choices is always possible, so such an a, b exist.

1.10 Translation bound

Berlekamp discovered the following important result.

Theorem 8 (Translation bound). If s is a winning N-state with N ≥ 3, and s^{(0)} ≥ 3, then Ts is a winning (N − 3)-state.

Proof. When N = 3, then any counterexample must have s^{(1)} ≥ 2; otherwise Ts would be a winning 0-state. But, together with the hypothesis, this implies that Vol_{3}(s) ≥ 3\binom{3}{0} + 2\binom{3}{1} = 3 · 1 + 2 · 3 = 9, which contradicts the volume bound, so s cannot be a winning 3-state.

If N > 3, proceed by induction. Write s = a + b, where Ta + b and a + Tb are winning (N − 1)-states. If a^{(1)} + b^{(0)} ≥ 3 and a^{(0)} + b^{(1)} ≥ 3, then by the induction hypothesis TTa + Tb and Ta + TTb are winning (N − 4)-states, so the partition Ts = Ta + Tb implies that Ts is a winning (N − 3)-state.

Otherwise, without loss of generality assume that a^{(0)} + b^{(1)} ≤ 2. Then s^{(1)} = a^{(1)} + b^{(1)} ≤ a^{(0)} + b^{(1)} ≤ 2. If s^{(1)} = 1, then Ts is a winning 0-state, so trivially a winning (N − 3)-state. If s^{(1)} = 2, let s′ be the state equal to s except that s′_{0} = 0. Then s′ is a winning N-state, since s′ ≤ s. But s′ is a doublet, so it is either a borderline winning N-state, or it is a winning (N − 1)-state. If s′ is a borderline winning N-state, then 2^{N} = Vol_{N}(s′) ≤ Vol_{N}(s) ≤ 2^{N}, so Vol_{N}(s) = Vol_{N}(s′), so s_{0} = 0, so s is a doublet, contradicting the hypothesis. On the other hand, if s′ is a winning (N − 1)-state, then Ts′ is a winning (N − 3)-state, by the formula for doublets, and Ts = Ts′, proving the desired result.

1.11 Infinite state sequences

Definition 14 (State sequence). A state sequence is an infinite sequence of states s_{0}, s_{1}, s_{2}, …, such that Ts_{i+1} = s_{i} for each i ≥ 0.

If the translation bound of the previous section applies to s_{1} (i.e., s_{1} is not a singlet or doublet), then it also applies to all of the subsequent states of the sequence. Then, if s_{0} is a winning N-state but not a winning (N − 1)-state, the translation bound implies that s_{1} may be a winning (N + 3)-state but cannot be a winning (N + 2)- state. And, in general, s_{n} may be a winning (N + 3n)-state but cannot be a winning (N + 3n − 1)-state.

We will be particularly interested in state sequences which achieve this bound:

Definition 15 (Winning N-state sequence). A state sequence is a winning Nstate sequence if s_{n} is a winning (N + 3n)-state, for every n.

Definition 16 (Borderline winning N-state sequence). A winning N-state sequence is a borderline winning N-state sequence if s_{n} is a borderline winning (N +3n)- state, for every n.

We can write a winning N-state sequence in the following compact form. Let

s_{0} = (s_{0}, s_{1}, …, s_{E})
s_{1} = (s_{−1}, s_{0}, s_{1}, …, s_{E})
s_{2} = (s_{−2}, s_{−1}, s_{0}, s_{1}, …, s_{E})

and so on. Then we can write the entire state sequence as the infinite tuple

s = (…, s_{−n}, s_{1−n}, …, s_{−1}; s_{0}, s_{1}, …, s_{E}).

(The semicolon indicates the first state in the state sequence.)

Definition 17 (Partial sums for state sequences). Given an infinite state sequence

s = (…, s_{−n}, s_{1−n}, …, s_{−1}; s_{0}, s_{1}, …, s_{E}),

we define

s^{(J)} = ∑_{J′=J}^{E} s_{J′}.

Definition 18 (Domination for state sequences). If s and t are infinite state sequences, we say that t dominates s if (and only if)

s^{(J)} ≤ t^{(J)} for all J.

We will use the notation t ≥ s for this relation.

Corollary 2 (Domination theorem for state sequences). If t dominates s, and t is a winning N-state sequence, then s is a winning N-state sequence.

Proof. Apply the domination theorem for states to s_{J} and t_{J}, for every J.

1.12 Fibonacci states

To use Corollary 2 to prove that a given state sequence is a winning N-state sequence, we need to have some winning N-state sequences to compare the given sequence to. Fortunately, Berlekamp discovered such sequences: in fact, the sequences he discovered are borderline winning N-state sequences.

A borderline winning N-state sequence is obviously highly constrained. If s_{0} is given, and is a borderline winning N-state, and we want s_{1} to be a borderline winning (N + 3)-state, then the value of s_{−1} is determined by the volume formula. We want to have Vol_{N+3}(s_{1}) = 2^{N+3}, so we must have

s_{−1} = 2^{N+3} − ∑_{J=0}^{E} s_{J} ∑_{J′=0}^{J+1} \binom{N + 3}{J′}.

If this formula gives a negative value for s_{−1}, then there is no borderline winning N-state sequence (indeed, no winning N-state sequence at all) beginning with s_{0}. If the formula gives a nonnegative value for s_{−1}, then we can determine

s_{−2} = 2^{N+6} − ∑_{J=−1}^{E} s_{J} ∑_{J′=0}^{J+2} \binom{N + 6}{J′}
s_{−3} = 2^{N+9} − ∑_{J=−2}^{E} s_{J} ∑_{J′=0}^{J+3} \binom{N + 9}{J′}

and so on. Only if s_{J} turns out to be nonnegative for every J is there a unique borderline winning N-state sequence beginning with s_{0}.

Berlekamp noticed that for certain starting states, the entire state sequence can be stated in closed form in terms of Fibonacci numbers. This makes it easy to see that the values are all nonnegative, so the state sequence exists. For example, the starting state (4, 1), which is a borderline winning 3-state, leads to the borderline winning 3-state sequence (…, 4414, 1042, 246, 58, 14; 4, 1).

We will call such a sequence a Fibonacci state sequence, and any state in such a sequence a Fibonacci state. Here are some more examples of Fibonacci state sequences:

(…, 7072, 1744, 352, 128, 0; 16)  (N = 4)
(…, 4408, 1048, 240, 64, 8; 8)  (N = 3)
(…, 2728, 644, 152, 36, 8; 4)  (N = 2)
(…, 1686, 398, 94, 22, 6; 2)  (N = 1)
(…, 4414, 1042, 246, 58, 14; 4, 1)  (N = 3)
(…, 2728, 644, 152, 36, 10; 1, 1)  (N = 2)
(…, 7142, 1686, 398, 94, 24; 5, 0, 1)  (N = 4)
(…, 4414, 1042, 246, 60, 15; 1, 0, 1)  (N = 3)
(…, 11556, 2728, 644, 154, 39; 6, 0, 0, 1)  (N = 5)
(…, 7142, 1686, 400, 99, 21; 1, 0, 0, 1)  (N = 4)
(…, 18698, 4414, 1044, 253, 60; 7, 0, 0, 0, 1)  (N = 6)
(…, 11556, 2730, 653, 159, 28; 1, 0, 0, 0, 1)  (N = 5)
(…, 30254, 7144, 1697, 412, 88; 8, 0, 0, 0, 0, 1)  (N = 7)
(…, 18700, 4427, 1065, 247, 36; 1, 0, 0, 0, 0, 1)  (N = 6)
(…, 48954, 11571, 2762, 659, 124; 9, 0, 0, 0, 0, 0, 1)  (N = 8)
(…, 30271, 7189, 1724, 371, 45; 1, 0, 0, 0, 0, 0, 1). (N = 7)

Theorem 9 (Fibonacci state sequences). There exist (unique) borderline winning N-state sequences, as follows:

• With E = 0 and 1 ≤ N ≤ 4, where the borderline winning N-state is just (2^{N}).

• With E ≥ 1 and N = E + 1, where the borderline winning N-state has the form (s_{0} = 1, 0, 0, …, 0, s_{E} = 1).

• With E ≥ 1 and N = E + 2, where the borderline winning N-state has the form (s_{0} = N + 1, 0, 0, …, 0, s_{E} = 1).

Chapter 2

Computational methods

2.1 Summation rule for states

Suppose that c and d are winning (N − 1)-states. For which states s does this information suffice to show that s is a winning N-state?

If we can construct a, b such that s = a + b, Ta + b ≤ c, and a + Tb ≤ d, then we can conclude that s is a winning N-state.

Theorem 10 (Summation theorem for states). Given states s, c, d, the following are necessary and sufficient conditions for the existence of states a, b such that s = a + b, Ta + b ≤ c, and a + Tb ≤ d:

s^{(J+1)} ≤ c^{(J)}
s^{(J+1)} ≤ d^{(J)}
s^{(J)} + s^{(J+1)} ≤ c^{(J)} + d^{(J)},

for all J = 0, 1, …, E. (Note that s^{(E+1)} is zero by definition.)

Proof. The conditions are clearly necessary, since:

Ta + b ≤ c ⟹ s^{(J+1)} = a^{(J+1)} + b^{(J+1)} ≤ a^{(J+1)} + b^{(J)} ≤ c^{(J)}
a + Tb ≤ d ⟹ s^{(J+1)} = a^{(J+1)} + b^{(J+1)} ≤ a^{(J)} + b^{(J+1)} ≤ d^{(J)}
Ta + b + a + Tb ≤ c + d ⟹ s^{(J)} + s^{(J+1)} = a^{(J)} + b^{(J)} + a^{(J+1)} + b^{(J+1)} ≤ c^{(J)} + d^{(J)}.

To show the conditions are sufficient, for each J, we need to find a^{(J)}, and b^{(J)} = s^{(J)} − a^{(J)}, such that all of the following inequalities are simultaneously satisfied:

a^{(J+1)} ≤ a^{(J)} ⟺ a^{(J)} ≥ a^{(J+1)}
b^{(J+1)} ≤ b^{(J)} ⟺ a^{(J)} ≤ s^{(J)} − b^{(J+1)}
a^{(J+1)} + b^{(J)} ≤ c^{(J)} ⟺ a^{(J)} ≥ a^{(J+1)} + s^{(J)} − c^{(J)}
a^{(J)} + b^{(J+1)} ≤ d^{(J)} ⟺ a^{(J)} ≤ d^{(J)} − b^{(J+1)}.

(Recall that a^{(E+1)} = b^{(E+1)} = 0 by definition.)

Once a valid choice of a^{(J+1)} has been made, there exists at least one value for a^{(J)} that simultaneously satisfies all of these inequalities, because:

a^{(J+1)} ≤ s^{(J)} − b^{(J+1)} ⟺ s^{(J+1)} ≤ s^{(J)}
a^{(J+1)} ≤ d^{(J)} − b^{(J+1)} ⟺ s^{(J+1)} ≤ d^{(J)}
a^{(J+1)} + s^{(J)} − c^{(J)} ≤ s^{(J)} − b^{(J+1)} ⟺ s^{(J+1)} ≤ c^{(J)}
a^{(J+1)} + s^{(J)} − c^{(J)} ≤ d^{(J)} − b^{(J+1)} ⟺ s^{(J)} + s^{(J+1)} ≤ c^{(J)} + d^{(J)}.

The first follows from the definition of s^{(J)}, and the next three are the hypotheses of the theorem. Definition 19 (Summation for states). If c, d are states, we will write c ⊕ d for the set of states s that satisfy the inequalities:

s^{(J+1)} ≤ c^{(J)}
s^{(J+1)} ≤ d^{(J)}
s^{(J)} + s^{(J+1)} ≤ c^{(J)} + d^{(J)},

for J = 0, 1, …, E.

Note that if s = a + b, then s ∈ (Ta + b) ⊕ (a + Tb). But c ⊕ d is well-defined even if there is no pair of states a, b such that c = Ta + b and d = a + Tb, as will often be the case. Corollary 3. If c, d are winning (N − 1)-states, and s ∈ c ⊕ d, then s is a winning N-state. Corollary 4. If s = a + b, Ta + b ≤ c, and a + Tb ≤ d, then s ∈ c ⊕ d.

2.2 Summation rule for state sequences

Theorem 11 (Summation theorem for state sequences). Given state sequences s, c, d, the following are necessary and sufficient conditions for the existence of state sequences a, b such that s = a + b, Ta + b ≤ c, and a + Tb ≤ d:

s^{(J+1)} ≤ c^{(J)}
s^{(J+1)} ≤ d^{(J)}
s^{(J)} + s^{(J+1)} ≤ c^{(J)} + d^{(J)},

for all J ≤ E. (Note that s^{(E+1)} is zero by definition.)

Proof. The proof is exactly the same as for Theorem 10, but now we consider all values of J ≤ E, instead of just J = 0, 1, …, E.

Definition 20 (Summation for state sequences). If c, d are state sequences, we will write c ⊕ d for the set of state sequences s that satisfy the inequalities:

s^{(J+1)} ≤ c^{(J)}
s^{(J+1)} ≤ d^{(J)}
s^{(J)} + s^{(J+1)} ≤ c^{(J)} + d^{(J)},

for all J ≤ E.

Corollary 5. If c, d are winning (N − 1)-state sequences, and s ∈ c ⊕ d, then s is a winning N-state sequence.

2.3 Game trees for states

One of our goals is to prove that certain states are winning N-states. Each such state will demonstrate the existence of an optimal adaptive block code for a particular choice of code parameters.

To do this, we will construct game trees. We know that we can prove that a state s is a winning N-state by writing s = a + b and proving that Ta + b and a + Tb are winning (N − 1)-states. Or, more generally, we can use Corollary 3. In this case, we need to exhibit c, d which are winning (N − 1)-states, such that s ∈ c ⊕ d.

In order to show that any state is a winning state this way, we have to have some winning states to start with. We have four sorts of states that we have previously shown to be winning N-states for appropriate choices of N: singlets (Section 1.5), doublets (Theorem 5), zero-error states (Theorem 6), and Fibonacci states (Section 1.12). Given two such winning N-states, we can then show that some other states are winning (N + 1)-states by using Corollary 3. Given two winning (N + 1)-states, we can show that another state is a winning (N + 2)-state, and so on.

We will represent this process of inference by a binary tree. If we check that each leaf is provably a winning N-state for the value of N at that leaf, and that each non-leaf satisfies Definition 19 with respect to its children, then we have a proof that the root of the tree is a winning N-state. Definition 21 (Game tree of states). A game tree of states is a finite binary tree in which each node contains a state s and an integer N ≥ 0. At each leaf, (s, N), s is provably a winning N-state: either a singlet, or a doublet (Theorem 5), or a zero-error state (Theorem 6), or a Fibonacci state (Theorem 9). Each non-leaf node, (s, N), has precisely two children, (c, N − 1) and (d, N − 1), such that s ∈ c ⊕ d. Theorem 12 (Game tree theorem for states). For every node (s, N) in a valid game tree of states, s is a winning N-state. Proof. At each leaf, s is provably a winning N-state, by the definition of the game tree. At each other node, Corollary 3 shows that the theorem holds at that node given that it holds at each child node. By induction on the tree, the theorem holds at every node.

In practice, many of the nodes with the same value N may contain the same state. In that case, we can collapse the tree so that we have only a single node with that state and value, and it is the child of several different parent nodes. It may also be the case that both children of a given node are equal, and again we can make them the same node. In this manner, we can greatly reduce the number of distinct nodes required to represent a proof that a given state is a winning N-state.

2.4 Game trees for state sequences

Another goal is to prove that certain infinite state sequences are winning Nstate sequences. Each such state sequence will demonstrate the existence of optimal adaptive block codes for an infinite collection of parameter choices.

In order to show that any state sequence is a winning state sequence, we have to have some winning state sequences to start with. For this purpose we will rely on the Fibonacci state sequences of Theorem 9. Given two such winning N-state sequences, we can then show that some other state sequences are winning (N +1)-state sequences by using Corollary 5. Given two winning (N + 1)-state sequences, we can show that another state is a winning (N + 2)-state sequence, and so on.

We can also represent this process of inference by a binary tree. If we check that each leaf is provably a winning N-state sequence for the value of N at that leaf, and that each non-leaf satisfies Definition 20 with respect to its children, then we have a proof that the root of the tree is a winning N-state sequence.

Definition 22 (Game tree of state sequences). A game tree of state sequences is a finite binary tree in which each node contains a state sequence s and an integer N. At each leaf, (s, N), s satisfies the criteria of Section 1.12. Each non-leaf node, (s, N), has precisely two children, (c, N − 1) and (d, N − 1), such that s ∈ c ⊕ d.

Theorem 13 (Game tree theorem for state sequences). For every node (s, N) in a valid game tree of state sequences, s is a winning N-state sequence.

Proof. At each leaf, s is provably a winning N-state sequence, by the definition of the game tree. At each other node, Corollary 5 shows that the theorem holds at that node given that it holds at each child node. By induction on the tree, the theorem holds at every node.

In practice, many of the nodes with the same value N may contain the same state sequence. In that case, we can collapse the tree so that we have only a single node with that state sequence and value, and it is the child of several different parent nodes. It may also be the case that both children of a given node are equal, and again we can make them the same node. In this manner, we can greatly reduce the number of distinct nodes required to represent a proof that a given state sequence is a winning N-state sequence.

2.5 Truncated state sequences

There is a practical problem with constructing game trees for state sequences: each node is supposed to contain an infinite state sequence, which would require infinite storage.

Fortunately, in some cases we can truncate the state sequences in a given game tree and still prove that the root node is a winning N-state sequence. Suppose that we have a state sequence with only finitely many nonzero coefficients: s = (…, 0, 0, 0; s_{0}, s_{1}, …, s_{E}). Suppose further that we have a game tree in the sense of Section 2.3 which proves that the state s_{0} = (s_{0}, s_{1}, …, s_{E}) is a winning N-state. Then, under certain additional conditions, we can conclude from that tree that s is a winning N-state sequence.

Theorem 14 (Truncated game tree theorem). Consider a game tree of states, with root (s_{0}, N), where s_{0} = (s_{0}, s_{1}, …, s_{E}) and M = s^{(0)}. Suppose that each node, (t_{0}, N′) contains a winning N′-state t_{0}. And suppose that each leaf, (t_{0}, N′), contains a winning N′-state t_{0} that can be extended to a winning N′-state sequence t such that t^{(−1)} ≥ M. Then s = (…, 0, 0, 0; s_{0}, s_{1}, …, s_{E}) is a winning N-state sequence.

Proof. From the given game tree of states, construct a game tree of state sequences as follows. Replace each node (t_{0}, N′), containing a state t_{0}, with a node (t, N), containing a state sequence t, such that:

t^{(J)} = \begin{cases}min(t_{0}^{(J)}, M) & if J ≥ 0, \\ M & if J < 0, \end{cases}

The root of the new tree is (s, N), by construction. At each leaf node (t, N′), the constructed state sequence t is dominated by the state sequence provided in the hypothesis of the theorem, so is a winning N′-state sequence.

It remains to show that Definition 20 holds at each node that is not a leaf. Consider such a node, (t, N′), with children (c, N′ − 1), (d, N′ − 1). The given game tree of states had corresponding nodes (t_{0}, N′), (c_{0}, N′ − 1), (d_{0}, N′ − 1), with t_{0} ∈ c_{0} ⊕ d_{0}. From Definition 19, we know that:

t_{0}^{(J+1)} ≤ c_{0}^{(J)}
t_{0}^{(J+1)} ≤ d_{0}^{(J)}
t_{0}^{(J)} + t_{0}^{(J+1)} ≤ c_{0}^{(J)} + d_{0}^{(J)},

for J = 0, 1, …, E.

For J ≤ −1:

t^{(J+1)} ≤ M = c^{(J)}
t^{(J+1)} ≤ M = d_{0}^{(J)}
t^{(J)} + t^{(J+1)} ≤ 2M = c_{0}^{(J)} + d_{0}^{(J)}.

For J ≥ 0:

t^{(J+1)} = min(t_{0}^{(J+1)}, M) ≤ min(c_{0}^{(J)}, M) = c^{(J)}
t^{(J+1)} = min(t_{0}^{(J+1)}, M) ≤ min(d_{0}^{(J)}, M) = d^{(J)}
t^{(J)} + t^{(J+1)} = min(t_{0}^{(J)}, M) + min(t_{0}^{(J+1)}, M) ≤ min(c_{0}^{(J)}, M) + min(d_{0}^{(J)}, M) = c^{(J)} + d^{(J)}.

Thus all the conditions of Definition 20 are satisfied, so t ∈ c ⊕ d.

Since this holds at every non-leaf node, and every leaf node contains a winning N′-state sequence, the constructed game tree is a valid game tree of state sequences, so s is a winning N-state sequence.

2.6 Losing states

We have previously stated two criteria by which to show that an N-state is a losing N-state (i.e., not a winning N-state). One is the volume bound of Section 1.5, and the other is the translation bound of Section 1.10. For our characterization of optimal adaptive block codes, we need some additional results to show that certain N-states are losing N-states.

Theorem 15 (First step). If s = (0, 0, …, 0, 0, s_{E}) is a winning N-state, with E > 0, then t = (0, 0, …, 0, ⌊s_{E}/2⌋, ⌈s_{E}/2⌉) is a winning (N − 1)-state. If s_{E} is odd, then Vol_{N}(s) ≤ 2^{N} − \binom{N−1}{E}.

Proof. Suppose that s = a + b where c = Ta + b and d = a + Tb are winning (N − 1)-states. Then s_{E} = a_{E} + b_{E}, so either a_{E} ≥ ⌈s_{E}/2⌉ or b_{E} ≥ ⌈s_{E}/2⌉. Since c^{(E)} = b_{E}, d^{(E)} = a_{E}, and c^{(J)} = d^{(J)} = s_{E} for J < E, either t ≤ c or t ≤ d. In either case, t is a winning (N − 1)-state.

If E is odd, then

t = (0, 0, …, 0, (s_{E} − 1)/2, (s_{E} + 1)/2)

is a winning (N − 1)-state, so:

Vol_{N−1}(t) = \frac{s_{E} − 1}{2} ∑_{J=0}^{E−1} \binom{N − 1}{E} + \frac{s_{E} + 1}{2} ∑_{J=0}^{E−1} \binom{N − 1}{J}

= s_{E} ∑_{J=0}^{E−1} \binom{N − 1}{J} + \frac{s_{E} + 1}{2}\binom{N − 1}{E}

≤ 2^{N−1}.

Then:

Vol_{N}(s) = s_{E} ∑_{J=0}^{E} \binom{N}{J}

= s_{E} ∑_{J=0}^{E} \binom{N − 1}{J} + s_{E} ∑_{J=0}^{E} \binom{N − 1}{J − 1}

= 2s_{E} ∑_{J=0}^{E−1} \binom{N − 1}{J} + s_{E}\binom{N − 1}{E}

= 2 Vol_{N−1}(t) − \binom{N − 1}{E}

≤ 2 · 2^{N−1} − \binom{N − 1}{E}.

Theorem 16 (Second step). Suppose that s = (0, 0, …, 0, 0, s_{E−1}, s_{E}) is a winning N-state, with E > 1. Let g = gcd (\binom{N−1}{E}, \binom{N−1}{E−1}). Write \binom{N−1}{E} = kg and \binom{N−1}{E−1} = ℓg. Suppose that s_{E}k + s_{E−1}ℓ is odd. Then Vol_{N}(s) ≤ 2^{N} − g.

Proof. Write s = a + b such that Ta + b and a + Tb are winning (N − 1)-states. By conservation of volume, Vol_{N−1}(Ta + b) + Vol_{N−1}(a + Tb) = Vol_{N}(s). Without loss of generality, assume Vol_{N−1}(a + Tb) ≥ Vol_{N}(s)/2. Let δ_{E} = 2a_{E} − s_{E} and δ_{E−1} = 2a_{E−1} − s_{E−1}. Then:

a + Tb = (0, 0, …, 0, (s_{E−1} − δ_{E−1})/2, (s_{E} + s_{E−1} − δ_{E} + δ_{E−1})/2, (s_{E} + δ_{E})/2),

so

Vol_{N−1}(a + Tb) = s_{E−1} ∑_{J=0}^{E−2} \binom{N − 1}{J} + \frac{s_{E−1} + δ_{E−1}}{2} \binom{N − 1}{E − 1}

+ s_{E} ∑_{J=0}^{E−1} \binom{N − 1}{J} + \frac{s_{E} + δ_{E}}{2} \binom{N − 1}{E}.

Then:

Vol_{N}(s) = s_{E−1} ∑_{J=0}^{E−1} \binom{N}{J} + s_{E} ∑_{J=0}^{E} \binom{N}{J}

= 2s_{E−1} ∑_{J=0}^{E−2} \binom{N − 1}{J} + s_{E−1}\binom{N − 1}{E − 1} + 2s_{E} ∑_{J=0}^{E−1} \binom{N − 1}{J} + s_{E}\binom{N − 1}{E}

= 2 Vol_{N−1}(a + Tb) − δ_{E−1}\binom{N − 1}{E − 1} − δ_{E}\binom{N − 1}{E}

= 2 Vol_{N−1}(a + Tb) − g(δ_{E}k + δ_{E−1}ℓ).

But δ_{E} ≡ s_{E} (mod 2) and δ_{E−1} ≡ s_{E−1} (mod 2), so

δ_{E}k + δ_{E−1}ℓ ≡ s_{E}k + s_{E−1}ℓ ≡ 1 (mod 2),

so δ_{E}k + δ_{E−1}ℓ is not zero. Since Vol_{N−1}(a + Tb) ≥ Vol_{N}(s)/2, δ_{E}k + δ_{E−1}ℓ must be a positive integer, so Vol_{N}(s) ≤ 2 Vol_{N−1}(a + Tb) − g ≤ 2^{N} − g.

2.7 A three-step losing state

We want to demonstrate one more losing state, not covered by Theorem 15 or Theorem 16 of the previous section. Rather than generalize to other states, we will consider only the specific result we need. Of course, a generalization of this calculation would be possible.

Theorem 17 (Three-step theorem). The 37-state

s = (0, 0, 0, 0, 0, 0, 48475)

is a losing 37-state.

Proof. Assume that s is a winning 37-state. Then, by Theorem 15,

t = (0, 0, 0, 0, 0, 24237, 24238)
Vol_{36}(t) = 68719133896

is a winning 36-state. So there exist a, b such that t = a + b and Ta + b, a + Tb are winning 35-states. Choose δ_{5}, δ_{6} such that:

a = (0, 0, 0, 0, 0, (24237 − δ_{5})/2, (24238 − δ_{6})/2)
b = (0, 0, 0, 0, 0, (24237 + δ_{5})/2, (24238 + δ_{6})/2).

Since Vol_{36}(t) = Vol_{35}(Ta + b) + Vol_{35}(a + Tb), assume without loss of generality that Vol_{35}(Ta + b) ≥ Vol_{36}(t)/2. So

u = Ta + b = (0, 0, 0, 0, (24237 − δ_{5})/2, (48475 − δ_{6} + δ_{5})/2, (24238 + δ_{6})/2)
Vol_{35}(u) = 34359566948 + 162316δ_{5} + 811580δ_{6}
= 34359566948 + 162316(δ_{5} + 5δ_{6})

is a winning 35-state. But in order for the elements of a to be integers, δ_{5} must be odd and δ_{6} must be even, so δ_{5} + 5δ_{6} is odd, and positive since Vol_{35}(u) ≥ Vol_{36}(t)/2 = 34359566948.

But if δ_{5} + 5δ_{6} ≥ 3, then

Vol_{35}(u) ≥ 34359566948 + 3 · 162316 = 34360053896 > 2^{35}.

So δ_{5} + 5δ_{6} = 1, so δ_{5} = 1 − 5δ_{6}, so

u = (0, 0, 0, 0, (24236 + 5δ_{6})/2, (48476 − 6δ_{6})/2, (24238 + δ_{6})/2)
Vol_{35}(u) = 34359566948 + 162316 = 34359729264

is a winning 35-state. So there exist c, d such that u = c + d and Tc + d, c + Td are winning 34-states. Choose ϵ_{4}, ϵ_{5}, ϵ_{6} such that:

c = (0, 0, 0, 0, (24236 + 5δ_{6} − ϵ_{4})/4, (48476 − 6δ_{6} − ϵ_{5})/4, (24238 + δ_{6} − ϵ_{6})/4)
d = (0, 0, 0, 0, (24236 + 5δ_{6} + ϵ_{4})/4, (48476 − 6δ_{6} + ϵ_{5})/4, (24238 + δ_{6} + ϵ_{6})/4).

Since Vol_{35}(u) = Vol_{34}(Tc + d) + Vol_{34}(c + Td), assume without loss of generality that Vol_{34}(Tc + d) ≥ Vol_{35}(u)/2. So

v = Tc + d = (0, 0, 0, (24236 + 5δ_{6} − ϵ_{4})/4, (72712 − δ_{6} − ϵ_{5} + ϵ_{4})/4, (72714 − 5δ_{6} − ϵ_{6} + ϵ_{5})/4, (24238 + δ_{6} + ϵ_{6})/4)

Vol_{34}(v) = 17179864632 + 11594ϵ_{4} + 69564ϵ_{5} + 336226ϵ_{6}
= 17179864632 + 11594(ϵ_{4} + 6ϵ_{5} + 29ϵ_{6}).

is a winning 34-state. But in order for the elements of c to be integers,

ϵ_{4} ≡ 24236 + 5δ_{6} ≡ δ_{6} (mod 4)
ϵ_{5} ≡ 48476 − 6δ_{6} ≡ 2δ_{6} (mod 4)
ϵ_{6} ≡ 24238 + δ_{6} ≡ 2 + δ_{6} (mod 4)
ϵ_{4} + 6ϵ_{5} + 29ϵ_{6} ≡ ϵ_{4} + 2ϵ_{5} + ϵ_{6} ≡ 2 + 2δ_{6} ≡ 2 (mod 4).

But ϵ_{4} + 6ϵ_{5} + 29ϵ_{6} cannot be negative, since Vol_{34}(v) ≥ Vol_{35}(u)/2 = 17179864632, so ϵ_{4} + 6ϵ_{5} + 29ϵ_{6} is at least 2, so

Vol_{34}(v) ≥ 17179864632 + 2 · 11594 = 17179887820 > 2^{34}.

So v cannot be a winning 34-state. Corollary 6. There is no adaptive block code with N = 37, E = 5, and M = 48475.

Chapter 3

Optimal codes

3.1 Main Result

When M = 1 or M = 2, determining when an adaptive error-correcting code exists is trivial; see Sections 1.5 and 1.7. (When M = 1, the code always exists. When M = 2, the code exists iff N ≥ 2E + 1.) Our main result is to completely determine necessary and sufficient conditions for the existence of adaptive error-correcting codes, for all values of M up to 2^{20}.

Definition 23 (Optimal code). An optimal adaptive error-correcting code has parameters N, E, M such that there exists no adaptive error-correcting code with the same value of N and E and a larger value of M.

Theorem 18 (Optimal codes). The optimal adaptive error-correcting codes with 3 ≤ M ≤ 2^{20} are precisely those shown in Table 3.1.

Corollary 7 (Main result). If 3 ≤ M ≤ 2^{20}, there exists an adaptive block code with parameters N, E, M if and only if M is less than or equal to the value indexed by N and E in Table 3.1, or if N is greater than the largest value indexed for E in Table 3.1.

The proof combines the techniques of Chapter 2 with a large computation, to construct search trees demonstrating the existence of the codes in Table 3.1. The fact 31

N  E = 0 E = 1 E = 2 E = 3 E = 4 E = 5 E = 6 E = 7 E = 8 E = 9 E ≥ 10
3E + 2  4  4  4  4  4  4  4  4  4  4  4
3E + 3  8  8  8  8  8  8  8  8  8  8  8
3E + 4  16  16  16  16  16  16  16  16  16  16  16
3E + 5  32  28  28  28  28  28  28  28  28  28  28
3E + 6  64  50  50  50  50  50  50  50  50  50  50
3E + 7  128  92  88  88  88  88  88  88  88  88  88
3E + 8  256  170  154  154  154  154  154  154  154  154  154
3E + 9  512  314  270  264  264  264  264  264  264  264  264
3E + 10  1024  584  478  451  451  451  451  451  451  451  451
3E + 11  2048 1092  850  776  768  768  768  768  768  768  768
3E + 12  4096 2048 1524 1342  1294 1294 1294 1294  1294 1294  1294
3E + 13  8192 3854 2744 2337  2196 2192 2192 2192  2192 2192  2192
3E + 14 16384 7280 4968 4096  3748 3662 3662 3662  3662 3662  3662
3E + 15 32768 13796 9038 7216  6436 6154 6154 6154  6154 6154  6154
3E + 16 65536 26214 16512 12776 11110 10406 10249 10249 10249 10249 10249
3E + 17 131072 49932 30282 22732 19282 17686 17116 17116 17116 17116 17116
3E + 18 262144 95324 55738 40622 33626 30216 28734 28467 28467 28467 28467
3E + 19 524288 182360 102926 72884 58904 51868 48474 47306 47306 47306 47306
3E + 20 1048576 349524 190650 131264 103620 89438 82160 78986 78589 78589 78589
3E + 21  671088 354136 237238 183005 154876 139866 132474 130088 130088 130088
3E + 22  659546 430184 324416 269268 239102 223138 216269 215900 215900
3E + 23  782468 577124 469928 410374 377388 361034 356245 356245
3E + 24  1030090 823076 706994 640756 605094 590174 590174
3E + 25  1017990 981464 972164

Table 3.1: Optimal Adaptive Codes with M ≤ 2^{20}

that each code is optimal (i.e., the nonexistence of adaptive codes with larger values of M) in each case follows from the results in Chapter 2.

3.2 Upper bounds on M

In order to show that each value in Table 3.1 is optimal, we need to show that increasing M by 1 makes it impossible to construct an adaptive error-correcting code. In each case, the result follows from results in Chapter 2. The symbols in Table 3.2 show which theorem applies in each case:

V: Theorem 3 (Volume bound)

1: Theorem 15 (First step)

2: Theorem 16 (Second step)

3: Theorem 17 (Third step)

T: Theorem 8 (Translation bound)

N  E = 0 E = 1 E = 2 E = 3 E = 4 E = 5 E = 6 E = 7 E = 8 E = 9 E ≥ 10
3E + 2  V  T  T  T  T  T  T  T  T  T  T
3E + 3  V  T  T  T  T  T  T  T  T  T  T
3E + 4  V  T  T  T  T  T  T  T  T  T  T
3E + 5  V  V  T  T  T  T  T  T  T  T  T
3E + 6  V  1  T  T  T  T  T  T  T  T  T
3E + 7  V  1  1  T  T  T  T  T  T  T  T
3E + 8  V  V  V  T  T  T  T  T  T  T  T
3E + 9  V  1  V  1  T  T  T  T  T  T  T
3E + 10  V  1  V  V  T  T  T  T  T  T  T
3E + 11  V  V  1  V  1  T  T  T  T  T  T
3E + 12  V  V  V  V  1  T  T  T  T  T  T
3E + 13  V  1  V  V  V  V  T  T  T  T  T
3E + 14  V  1  1  V  V  V  T  T  T  T  T
3E + 15  V  1  1  V  V  1  T  T  T  T  T
3E + 16  V  V  1  2  1  1  V  T  T  T  T
3E + 17  V  V  1  1  1  1  1  T  T  T  T
3E + 18  V  1  V  V  V  1  V  V  T  T  T
3E + 19  V  1  1  1  V  1  3  1  T  T  T
3E + 20  V  1  V  V  V  1  V  V  V  T  T
3E + 21  V  V  V  V  V  1  V  V  T  T
3E + 22  V  1  2  V  1  V  V  V  T
3E + 23  V  1  V  V  V  1  V  T
3E + 24  1  V  V  V  V  V  T
3E + 25  1  1  VT

Table 3.2: Derivation of Upper Bounds

Note that when E = 10 and N = 55, the result follows from the Volume bound; when E > 10 and N = 3E + 25, the result follows from the Translation bound.

When N < 3E + 2, no adaptive error-correcting code can have M > 2. If E = 0 and N = 1, M = 3 would violate the translation bound. If E > 0 and N = 3E + 1, then M = 3 would violate the volume bound. If N < 3E + 1, then M = 3 would violate Lemma 1.

To prove Theorem 18, it remains to show that: (1) for each entry in Table 3.1, an adaptive error-correcting code exists with the specified values of N, E, M; (2) for values of N greater than those in Table 3.1, an adaptive error-correcting code exists with M > 2^{20}.

3.3 Search algorithm for states

The results of Chapter 2 let us use search trees to demonstrate the existence of adaptive block codes. In this chapter we will describe the algorithms that allow us to construct search trees, and thus establish our main results.

Our basic approach is a recursive depth-first search, with memoization, for constructing search trees. The goal of the algorithm is to prove that a given N-state is a winning N-state. (In some cases, we will subsequently extend the analysis to show that a given N-state sequence is a winning N-state sequence.)

Memoization is a technique in which we record winning N′-states as we find them, so that later in the depth-first search, if we visit a state that is dominated by one of these states, we know that the new state is a winning state without further search.

Algorithm 1 (Depth-first search).

Input: An N-state s.

Output: A proof that s is a winning N-state, or failure.

Start: Initialize an empty table of winning N′-states, for each N′ ≤ N.

Procedure:

1. If s is provably a winning N-state (using Theorem 9), find t, a winning N-state which dominates s; go to step 9.

2. If s is provably a losing state (using Theorem 3, the volume bound, or Theorem 8, the translation bound), return failure.

3. Search the table of winning N-states for a winning N-state t which dominates s; if found, return t.

4. Choose states a and b such that s = a + b (using Algorithm 2).

5. Apply Algorithm 1 to the (N − 1)-state c = Ta + b. If the algorithm fails, go to step 8.

6. Apply Algorithm 1 to the (N − 1)-state d = a + Tb. If the algorithm fails, go to step 8.

7. If Algorithm 1 succeeds for c and d, returning c′ and d′ respectively, find t ∈ c′ ⊕ d′ which dominates s (using Algorithm 4); go to step 9.

8. If Algorithm 1 fails for c or d, repeat step 5 with a different choice of a and b (using Algorithm 3). If too many choices of a and b have already been tried, return failure.

9. Store the winning N-state t which dominates s in the table of winning N-states; return t.

Theorem 19 (Search theorem for states). If Algorithm 1 with input (s, N) returns with success, then s is a winning N-state.

Proof. The winning states found by Algorithm 1 form the game tree in the hypothesis of Theorem 12. The root of the tree contains (t, N), where t dominates s. The algorithm does not return with success unless the game tree is complete.

If Algorithm 1 returns failure, that does not imply that the state s cannot be a winning N-state, because not all possibilities for a, b are tried in step 4. However, in the cases we shall consider, when Algorithm 1 fails, we shall be able to show that s is not a winning N-state.

3.4 Partitioning algorithm

One key to Algorithm 1 is making a good choice of a and b in step 4. Of course, many different choices may work, and any choice that works leads to a correct proof. Because sometimes our first choice of a and b fails, we also need a method to generate additional candidates.

Algorithm 2 (Partitioning).

Input: An N-state s.

Output: A pair of states a, b such that s = a + b. Start: Procedure:

1. First step

2. Second step

3. Third step Algorithm 3 (Biased partitioning). Input: An N-state s. Output: A pair of states a, b such that s = a + b. Start: Initialize a vector .... Procedure:

1. First step

2. Second step

3. Third step

3.5 Summation algorithm

A second key to Algorithm 1 is choosing the state t ∈ c ⊕ d in step 7. Again, many different choices could work, and any choice that works leads to a correct proof. In general, we want to choose t as “large” as possible, so that when we store t in our table of winning N-states, we will be likely to later find other N-states in our search that are dominated by t.

The method we use, which works well in practice, is to make the lexicographically largest choice of t. That is, of all of the elements of c ⊕ d that dominate s, we choose t with t_{E} as large as possible. Among such states, we choose t with t_{E−1} as large as possible, and so on.

When applying Algorithm 1 to a root state s with s^{(0)} = M, all of the intermediate states in the game tree for s can be chosen to have t^{(0)} ≤ M. So, for convenience, we will also require that the state produced by Algorithm 4 has t^{(0)} ≤ M. This constraint has no effect on the success of the program; it simply lets us avoid computing and storing very large numbers that would otherwise occur.

This algorithm is implemented by the addstate function in Appendix A.

Algorithm 4 (Summation).

Input: An N-state s, (N −1)-states c, d such that s ∈ c⊕d, and an integer M ≥ s^{(0)}.

Output: An N-state t such that s ≤ t, t ∈ c ⊕ d, and t^{(0)} ≤ M, and which is lexicographically largest among all such t.

Start: Let s = (s_{0}, s_{1}, …, s_{E}).

Procedure:

1. Let t^{(E+1)} = 0.

2. In turn for J = E, J = E − 1, …, J = 0, let t^{(J)} = min(M, c^{(J−1)}, d^{(J−1)}, c^{(J)} +d^{(J)} −t^{(J+1)}, c^{(J−1)} +d^{(J−1)} −s^{(J−1)}, c^{(J−2)} + d^{(J−2)} − s^{(J−2)}).

3.6 Lifting game trees

If the game tree produced by Algorithm 1 with input (s_{0}, N) satisfies certain additional conditions, we can conclude not only that s_{0} = (s_{0}, s_{1}, …, s_{E}) is a winning N-state, but that s = (…, 0, 0, 0; s_{0}, s_{1}, …, s_{E}) is a winning N-state sequence. The conditions are given by Theorem 14: for each leaf of the game tree produced by Algorithm 1, (t_{0}, N′), it must be possible to extend t_{0} to a winning N′-state sequence t such that t^{(−1)} ≥ s^{(0)}.

This is a condition that we can check during the execution of Algorithm 1. The winning states which can be extended to winning state sequences are Fibonacci states (Section 1.12). So, if each leaf reached in the execution of Algorithm 1 is a Fibonacci state, with the desired property, then we can assert that s is a winning N-state sequence.

If all of the leaves are Fibonacci states, but not all have the desired property, then we can attempt to lift the game tree. Lifting starts at the leaves of the tree and proceeds toward the root. Lifting of each node assumes that the children of that node have been lifted.

Algorithm 5 (Lifting).

Input: A game tree with the N-state s_{0} = (s_{0}, s_{1}, …, s_{E}) at the root.

Output: A game tree with the (N + 3)-state s_{−1} = (0, s_{0}, s_{1}, …, s_{E}) at the root, or failure.

Start: Initialize ....

Procedure:

1. First step

2. Second step

3. Third step

3.7 Computational Results

Appendix A contains the program which implements Algorithms 1, 2, 3, 4, and 5. Appendix B contains the output of this program, which takes about 4 minutes to run on a 600 MHz Pentium III system.

Each line of the output displays the success or failure of Algorithm 1 to find an optimal adaptive block code, or the success or failure of Algorithm 5 to “lift” a game tree. When Algorithm 1 succeeds, then there exists an adaptive block code with parameters N, E, M. When Algorithm 5 succeeds, and when all of the leaves of the lifted game tree are “safe”, then Theorem 14 implies the existence of adaptive block codes with parameters N + 3k, E + k, M, for all k ≥ 0. Together, these results from Appendix B imply all of the numeric values in Table 3.1. Note that Algorithm 1 fails, in the cases in Appendix B, only when one of the results in Table 3.2 demonstrates that it must fail. This is what lets us conclude that the results in Table 3.1 are optimal.

Appendix B also contains results which imply that for all values of N larger than those shown in Table 3.1, there exists an adaptive block code with M > 2^{20} = 1048576. This completes the proof of Theorem 18 and Corollary 7.

Appendix A

Program Listing

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <values.h>
#include <math.h>
#define NMAX 126
#define EMAX 32
#define FEXP(n) (pow (2.0, (double) (n)))
typedef struct winstate {
  struct winstate *next;
  int ns;
  struct winstate *left, *right;
  int state[EMAX+1];
} winstate;
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
static double bico[128][128], wts[128][128];
static winstate *tree[NMAX+1];
static int mcurrent;
static int leafnodes, safeleaves;
static int treenodes, searchnodes;

int treesearch (int e, int n, int m);
int lifttree (int e, int n, int m);
winstate *depthsearch (int state[], int ns, int n);
void inittree (void);
winstate *addtree (int state[], int ns, int n,
   winstate *left, winstate *right);
winstate *memotest (int state[], int ns, int n);
void cleartree (void);
int igcd (int m, int n);
void initwts (void);
double weight (int state[], int ns, int n);
int stateleq (int state1[], int ns1, int state2[], int ns2);
int mbound (int m, int e);
void copystate (int copy[], int *nc, int state[], int ns);
int leaftest (int state[], int *nsp, int n, int *safe);
int sumtest (int sum[], int ns,
     int state1[], int ns1, int state2[], int ns2);
void addstate (int sum[], int *nsp,
       int state1[], int ns1, int state2[], int ns2);
int main (int argc, char **argv) {
  int win;
  int e, k, m, n;
  setvbuf (stdout, NULL, _IOLBF, BUFSIZ);
  setvbuf (stderr, NULL, _IOLBF, BUFSIZ);
  initwts ();
  inittree ();
  for (k=2; k<=25; k++) {
    for (e=1; e<=EMAX; e++) {
      n = 3 * e + k;
      printf ("\n");
      for (m = mbound(n,e); m > 0; m--) {
win = treesearch (e, n, m);
if (win) break;
      }
      if (m <= mbound(n+3, e+1)) {
win = lifttree(e, n, m);
if (win) break;
      }

  }
}
printf ("\n");
(void) treesearch (10, 56, 1048576);
return 0;
}

int treesearch (int e, int n, int m) {
int state[EMAX+1], ns;
winstate *wp;
int j;
cleartree();
ns = e + 1;
for (j=0; j<e; j++)
  state[j] = 0;
state[e] = m;
printf ("E=%d N=%d M=%d: ", e, n, m);
mcurrent = m;
leafnodes = safeleaves = 0;
wp = depthsearch (state, ns, n);
if (wp != 0) {
  printf ("OK, %d tree nodes, %d leaf nodes (%d safe).\n",
  treenodes, leafnodes, safeleaves);
  return 1;
} else {
  printf ("Failed, %d search nodes.\n", searchnodes);
  return 0;
}
}

int lifttree (int e, int n, int m) {
int state[EMAX+1];
winstate *wp;
int safe;
int ns, nn;

while (leafnodes > safeleaves) {
e += 1;
n += 3;
printf ("E=%d N=%d M=%d: ", e, n, m);
leafnodes = safeleaves = 0;
for (nn=n; nn>=3; nn--) {
  tree[nn] = tree[nn-3];
  tree[nn-3] = 0;
}
for (nn=3; nn<=n; nn++) {
  for (wp=tree[nn]; wp!=0; wp=wp->next) {
state[0] = 0;
copystate (state+1, &ns, wp->state, wp->ns);
ns++;
if (wp->left == 0) {
if (! leaftest (state, &ns, nn, &safe))
goto FAIL;
leafnodes++;
if (safe) safeleaves++;
} else {
if (! sumtest (state, ns, wp->left->state, wp->left->ns,
wp->right->state, wp->right->ns)) {
state[0] = 1;
ns = 1;
}
addstate (state, &ns, wp->left->state, wp->left->ns,
wp->right->state, wp->right->ns);
}
copystate (wp->state, &wp->ns, state, ns);
  }
}
if (tree[n]->state[e] != m) {
FAIL:
  printf ("lift failed.\n");
  return 0;
}
printf ("lift succeeded: %d leaf nodes (%d safe).\n",
leafnodes, safeleaves);

}
return (leafnodes == safeleaves);
}

winstate *depthsearch (int state[], int ns, int n) {
int cut[EMAX+1], left[EMAX+1], right[EMAX+1], bias[EMAX+1];
int temp[EMAX+1], nr, nt;
winstate *wp, *wpr, *wpl;
double z, v, w, cmin, cmax;
int j, jj, k, nn, biaslvl, safe;
searchnodes++;
/* Memo check */
wp = memotest (state, ns, n);
if (wp != 0) return wp;
/* Check for leaf nodes */
copystate (temp, &nt, state, ns);
if (leaftest (temp, &nt, n, &safe)) {
  leafnodes++;
  if (safe) safeleaves++;
  return addtree (temp, nt, n, 0, 0);
}
for (j=0; j<ns; j++)
  bias[j] = 0;
biaslvl = ns-1;
goto TRY;
RETRY:
if (bias[biaslvl] < 0)
  bias[biaslvl] = -bias[biaslvl];
else
  bias[biaslvl] = -bias[biaslvl] - 1;
if (bias[biaslvl] <= -3) {
  bias[biaslvl] = 0;
  do {
    biaslvl--;
    if (biaslvl == 0) return 0;

} while (state[biaslvl] == 0);
bias[biaslvl] = -1;
}
TRY:
for (j=0; j<ns; j++)
left[j] = right[j] = 0;
k = 0;
for (j=ns-1; j>=0; j--) {
if (state[j] == 0) {
cut[j] = 0;
continue;
}
k += state[j];
if (k == 1) {
if (bias[j] != 0) goto RETRY;
cut[j] = 0;
goto CUT;
}
if (k == 2) {
cut[j] = 1 + bias[j];
if (cut[j] < 0 || cut[j] > state[j]) goto RETRY;
goto CUT;
}
cmin = -MAXINT;
cmax = MAXINT;
for (jj=j; jj>=0; jj--) {
nn = n - 3*jj - 1;
/* Projected left gap if cut[0..j] == state[0..j] */
v = FEXP (nn) - weight (left+jj, ns-jj, nn) -
  weight (state+jj+1, j-jj, nn);
/* Projected right gap if cut[0..j] == 0 */
w = FEXP (nn) - weight (right+jj, ns-jj, nn) -
  weight (state+jj+1, j-jj, nn);
if (v < 0.0 || w < 0.0) goto RETRY;
cmin = MAX (cmin, (state[j] - v / bico[nn][j-jj]));
cmax = MIN (cmax, w / bico[nn][j-jj]);
}

  if (cmin > cmax)
    goto RETRY;
  z = floor (0.5 * (cmin + cmax + 1));
  z = MAX (z, 0.0);
  z = MIN (z, state[j]);
  cut[j] = z + bias[j];
  if (cut[j] < cmin || cut[j] > cmax) goto RETRY;
CUT:
  if (cut[j] < 0 || cut[j] > state[j]) goto RETRY;
  left[j] += state[j] - cut[j];
  right[j] += cut[j];
  if (j > 0) {
    left[j-1] += cut[j];
    right[j-1] += state[j] - cut[j];
  }
}
nr = ns;
while (nr > 0 && right[nr-1] == 0)
  nr--;
wpl = depthsearch (left, ns, n-1);
if (wpl == 0) goto RETRY;
wpr = depthsearch (right, nr, n-1);
if (wpr == 0) goto RETRY;
copystate (temp, &nt, state, ns);
addstate (temp, &nt, wpl->state, wpl->ns, wpr->state, wpr->ns);
return addtree (temp, nt, n, wpl, wpr);
}

void inittree () {
int n;
for (n=0; n<=NMAX; n++)
  tree[n] = 0;
treenodes = 0;
}

winstate *addtree
(int state[], int ns, int n, winstate *left, winstate *right) {
winstate *wp;
int j;
for (wp=tree[n]; wp!=0; wp=wp->next)
  if (stateleq (state, ns, wp->state, wp->ns))
    return wp;
treenodes++;
wp = tree[n];
tree[n] = (winstate *) malloc (sizeof (winstate));
tree[n]->next = wp;
tree[n]->ns = ns;
for (j=0; j<ns; j++)
  tree[n]->state[j] = state[j];
tree[n]->left = left;
tree[n]->right = right;
return tree[n];
}

winstate *memotest (int state[], int ns, int n) {
winstate *wp;
wp = tree[n];
while (wp != 0) {
  if (stateleq (state, ns, wp->state, wp->ns))
    return wp;
  wp = wp->next;
}
return 0;
}

void cleartree () {
int n;
winstate *wp, *wpnext;
for (n=0; n<=NMAX; n++) {

  wp = tree[n];
  while (wp != 0) {
    wpnext = wp->next;
    free (wp);
    wp = wpnext;
  }
  tree[n] = 0;
}
treenodes = 0;
searchnodes = 0;
}

int igcd (int m, int n) {
if (m < 0) m = -m;
if (n < 0) n = -n;
if (m > n) return igcd (n, m);
if (m == 0) return n;
return igcd (n % m, m);
}

void initwts (void) {
int g, j, n;
for (n=0; n<=NMAX; n++) {
  bico[n][0] = 1.0;
  wts[n][0] = 1.0;
  for (j=1; j<=n; j++) {
    g = igcd (n-j+1, j);
    bico[n][j] = (bico[n][j-1] / (j/g)) * ((n-j+1) / g);
    wts[n][j] = wts[n][j-1] + bico[n][j];
  }
}
}

double weight (int state[], int ns, int n) {
double w;
int j;
w = 0.0;

for (j=0; j<ns; j++) {
  w += state[j] * wts[n][j];
}
return w;
}

int stateleq (int state1[], int ns1, int state2[], int ns2) {
int j, k1, k2;
if (ns1 > ns2)
  return 0;
k1 = k2 = 0;
for (j=ns2-1; j>ns1-1; j--)
  k2 += state2[j];
for (j=ns1-1; j>=0; j--) {
  k1 += state1[j];
  k2 += state2[j];
  if (k2 >= mcurrent) return 1;
  if (k1 > k2) return 0;
}
return 1;
}

int mbound (int n, int e) {
int j, m;
double z, zz;
if (n < 2*e+1) {
  m = 1;
} else if (n <= 3*e) {
  m = 2;
} else {
  z = FEXP(n) / wts[n][e];
  for (j=1; j<=e; j++) {
    zz = FEXP(n-3*j) / wts[n-3*j][e-j];
    z = MIN (z, zz);
  }
  m = floor(z);
}

return m;
}

void copystate (int copy[], int *nc, int state[], int ns) {
int i;
*nc = ns;
for (i=0; i<ns; i++)
  copy[i] = state[i];
}

int leaftest (int state[], int *nsp, int n, int *safe) {
int leafstate[EMAX+2];
double w;
int i, k, nn, ns;
ns = *nsp;
nn = n - 3 * (ns-1);
if (nn > 4)
  return 0;
leafstate[ns] = (nn >= 0) ? (1 << nn) : 1;
for (i=0; i<ns; i++)
  leafstate[i] = 0;
k = leafstate[ns];
for (i=1; i<ns; i++) {
  nn += 3;
  if (nn < i+1) continue;
  w = FEXP(nn) - weight (leafstate+(ns-i), i+1, nn);
  if (w >= mcurrent-k) {
    leafstate[ns-i] = mcurrent - k;
    k = mcurrent;
    break;
  }
  leafstate[ns-i] = w;
  k += leafstate[ns-i];
}
if (! stateleq (state, ns, leafstate+1, ns))

  return 0;
copystate (state, nsp, leafstate+1, ns);
*safe = (k >= mcurrent);
return 1;
}

int sumtest
(int sum[], int ns, int state1[], int ns1, int state2[], int ns2) {
int accum, accum1, accum2;
int i;
if (ns1 < ns-1 || ns2 < ns-1) return 0;
accum = sum[ns-1];
accum1 = 0;
for (i=ns-1; i<ns1; i++)
  accum1 += state1[i];
accum2 = 0;
for (i=ns-1; i<ns2; i++)
  accum2 += state2[i];
if (accum > accum1 + accum2) return 0;
for (i=ns-2; i>=0; i--) {
  accum1 += state1[i];
  accum2 += state2[i];
  if (accum > accum1) return 0;
  if (accum > accum2) return 0;
  if (sum[i] + 2*accum > accum1 + accum2) return 0;
  accum += sum[i];
}
return 1;
}

void addstate
(int sum[], int *nsp, int state1[], int ns1, int state2[], int ns2) {
int accum[EMAX+1], accum1[EMAX+1], accum2[EMAX+1];
int ns, i, j, k;
/* Ensure that output(sum[]) .ge. input(sum[]). */

ns = *nsp;
ns = MAX (ns, ns1);
ns = MAX (ns, ns2);
accum[ns] = accum1[ns] = accum2[ns] = 0;
for (i=ns-1; i>=0; i--) {
  accum[i] = accum[i+1] + (i < *nsp ? sum[i] : 0);
  accum1[i] = accum1[i+1] + (i < ns1 ? state1[i] : 0);
  accum2[i] = accum2[i+1] + (i < ns2 ? state2[i] : 0);
}
for (j=ns-1; j>=0; j--) {
  k = mcurrent;
  k = MIN (k, accum1[j] + accum2[j] - accum[j+1]);
  if (j > 0) k = MIN (k, accum1[j-1]);
  if (j > 0) k = MIN (k, accum2[j-1]);
  if (j > 0) k = MIN (k, accum1[j-1] + accum2[j-1] - accum[j-1]);
  if (j > 1) k = MIN (k, accum1[j-2] + accum2[j-2] - accum[j-2]);
  accum[j] = k;
}
while (ns > 0 && accum[ns-1] == 0)
  ns--;
*nsp = ns;
sum[ns-1] = accum[ns-1];
for (j=ns-2; j>=0; j--) {
  accum[j] = MIN (accum[j], mcurrent);
  sum[j] = accum[j] - accum[j+1];
}
assert (sumtest (sum, ns, state1, ns1, state2, ns2));
}

Appendix B

Program Output

E=1 N=5 M=4: OK, 1 tree nodes, 1 leaf nodes (1 safe).
E=1 N=6 M=8: OK, 1 tree nodes, 1 leaf nodes (1 safe).
E=1 N=7 M=16: OK, 1 tree nodes, 1 leaf nodes (1 safe).
E=1 N=8 M=28: OK, 9 tree nodes, 4 leaf nodes (0 safe).
E=2 N=11 M=28: lift succeeded: 4 leaf nodes (2 safe).
E=3 N=14 M=28: lift succeeded: 4 leaf nodes (4 safe).
E=1 N=9 M=51: Failed, 1 search nodes.
E=1 N=9 M=50: OK, 12 tree nodes, 4 leaf nodes (0 safe).
E=2 N=12 M=50: lift failed.
E=2 N=12 M=51: Failed, 1 search nodes.
E=2 N=12 M=50: OK, 22 tree nodes, 8 leaf nodes (0 safe).
E=3 N=15 M=50: lift succeeded: 8 leaf nodes (4 safe).
E=4 N=18 M=50: lift succeeded: 8 leaf nodes (8 safe).
E=1 N=10 M=93: Failed, 1 search nodes.
E=1 N=10 M=92: OK, 13 tree nodes, 3 leaf nodes (0 safe).
E=2 N=13 M=89: Failed, 1 search nodes.
E=2 N=13 M=88: OK, 25 tree nodes, 8 leaf nodes (0 safe).
E=3 N=16 M=88: lift succeeded: 8 leaf nodes (1 safe).
E=4 N=19 M=88: lift succeeded: 8 leaf nodes (6 safe).
E=5 N=22 M=88: lift succeeded: 8 leaf nodes (8 safe).

E=1 N=11 M=170: OK, 16 tree nodes, 3 leaf nodes (0 safe).
E=2 N=14 M=154: OK, 31 tree nodes, 7 leaf nodes (0 safe).
E=3 N=17 M=154: lift succeeded: 7 leaf nodes (0 safe).
E=4 N=20 M=154: lift succeeded: 7 leaf nodes (3 safe).
E=5 N=23 M=154: lift succeeded: 7 leaf nodes (7 safe).
E=1 N=12 M=315: Failed, 1 search nodes.
E=1 N=12 M=314: OK, 18 tree nodes, 3 leaf nodes (0 safe).
E=2 N=15 M=270: OK, 34 tree nodes, 6 leaf nodes (0 safe).
E=3 N=18 M=265: Failed, 1 search nodes.
E=3 N=18 M=264: OK, 54 tree nodes, 9 leaf nodes (0 safe).
E=4 N=21 M=264: lift succeeded: 9 leaf nodes (0 safe).
E=5 N=24 M=264: lift succeeded: 9 leaf nodes (4 safe).
E=6 N=27 M=264: lift succeeded: 9 leaf nodes (9 safe).
E=1 N=13 M=585: Failed, 1 search nodes.
E=1 N=13 M=584: OK, 18 tree nodes, 3 leaf nodes (0 safe).
E=2 N=16 M=478: OK, 39 tree nodes, 5 leaf nodes (0 safe).
E=3 N=19 M=451: OK, 116 tree nodes, 9 leaf nodes (0 safe).
E=4 N=22 M=451: lift succeeded: 9 leaf nodes (0 safe).
E=5 N=25 M=451: lift succeeded: 9 leaf nodes (1 safe).
E=6 N=28 M=451: lift succeeded: 9 leaf nodes (7 safe).
E=7 N=31 M=451: lift succeeded: 9 leaf nodes (9 safe).
E=1 N=14 M=1092: OK, 21 tree nodes, 3 leaf nodes (0 safe).
E=2 N=17 M=851: Failed, 1 search nodes.
E=2 N=17 M=850: OK, 40 tree nodes, 5 leaf nodes (0 safe).
E=3 N=20 M=776: OK, 67 tree nodes, 9 leaf nodes (0 safe).
E=4 N=23 M=769: Failed, 1 search nodes.
E=4 N=23 M=768: OK, 74 tree nodes, 13 leaf nodes (0 safe).
E=5 N=26 M=768: lift succeeded: 13 leaf nodes (0 safe).
E=6 N=29 M=768: lift succeeded: 13 leaf nodes (3 safe).
E=7 N=32 M=768: lift succeeded: 13 leaf nodes (10 safe).

E=8 N=35 M=768: lift succeeded: 13 leaf nodes (13 safe).
E=1 N=15 M=2048: OK, 14 tree nodes, 2 leaf nodes (0 safe).
E=2 N=18 M=1524: OK, 45 tree nodes, 5 leaf nodes (0 safe).
E=3 N=21 M=1342: OK, 86 tree nodes, 8 leaf nodes (0 safe).
E=4 N=24 M=1295: Failed, 1 search nodes.
E=4 N=24 M=1294: OK, 131 tree nodes, 11 leaf nodes (0 safe).
E=5 N=27 M=1294: lift succeeded: 11 leaf nodes (0 safe).
E=6 N=30 M=1294: lift succeeded: 11 leaf nodes (0 safe).
E=7 N=33 M=1294: lift succeeded: 11 leaf nodes (6 safe).
E=8 N=36 M=1294: lift succeeded: 11 leaf nodes (11 safe).
E=1 N=16 M=3855: Failed, 1 search nodes.
E=1 N=16 M=3854: OK, 26 tree nodes, 3 leaf nodes (0 safe).
E=2 N=19 M=2744: OK, 47 tree nodes, 4 leaf nodes (0 safe).
E=3 N=22 M=2337: OK, 122 tree nodes, 7 leaf nodes (0 safe).
E=4 N=25 M=2196: OK, 151 tree nodes, 10 leaf nodes (0 safe).
E=5 N=28 M=2192: OK, 331 tree nodes, 15 leaf nodes (0 safe).
E=6 N=31 M=2192: lift succeeded: 15 leaf nodes (0 safe).
E=7 N=34 M=2192: lift succeeded: 15 leaf nodes (1 safe).
E=8 N=37 M=2192: lift succeeded: 15 leaf nodes (8 safe).
E=9 N=40 M=2192: lift succeeded: 15 leaf nodes (13 safe).
E=10 N=43 M=2192: lift succeeded: 15 leaf nodes (15 safe).
E=1 N=17 M=7281: Failed, 1 search nodes.
E=1 N=17 M=7280: OK, 25 tree nodes, 3 leaf nodes (0 safe).
E=2 N=20 M=4969: Failed, 1 search nodes.
E=2 N=20 M=4968: OK, 46 tree nodes, 4 leaf nodes (0 safe).
E=3 N=23 M=4096: OK, 43 tree nodes, 6 leaf nodes (0 safe).
E=4 N=26 M=3748: OK, 161 tree nodes, 9 leaf nodes (0 safe).
E=5 N=29 M=3662: OK, 276 tree nodes, 13 leaf nodes (0 safe).

E=6 N=32 M=3662: lift succeeded: 13 leaf nodes (0 safe).
E=7 N=35 M=3662: lift succeeded: 13 leaf nodes (0 safe).
E=8 N=38 M=3662: lift succeeded: 13 leaf nodes (1 safe).
E=9 N=41 M=3662: lift succeeded: 13 leaf nodes (8 safe).
E=10 N=44 M=3662: lift succeeded: 13 leaf nodes (13 safe).
E=1 N=18 M=13797: Failed, 1 search nodes.
E=1 N=18 M=13796: OK, 29 tree nodes, 3 leaf nodes (0 safe).
E=2 N=21 M=9039: Failed, 1 search nodes.
E=2 N=21 M=9038: OK, 57 tree nodes, 4 leaf nodes (0 safe).
E=3 N=24 M=7216: OK, 86 tree nodes, 6 leaf nodes (0 safe).
E=4 N=27 M=6436: OK, 171 tree nodes, 9 leaf nodes (0 safe).
E=5 N=30 M=6155: Failed, 1 search nodes.
E=5 N=30 M=6154: OK, 276 tree nodes, 12 leaf nodes (0 safe).
E=6 N=33 M=6154: lift succeeded: 12 leaf nodes (0 safe).
E=7 N=36 M=6154: lift succeeded: 12 leaf nodes (0 safe).
E=8 N=39 M=6154: lift succeeded: 12 leaf nodes (0 safe).
E=9 N=42 M=6154: lift succeeded: 12 leaf nodes (3 safe).
E=10 N=45 M=6154: lift succeeded: 12 leaf nodes (10 safe).
E=11 N=48 M=6154: lift succeeded: 12 leaf nodes (12 safe).
E=1 N=19 M=26214: OK, 32 tree nodes, 3 leaf nodes (0 safe).
E=2 N=22 M=16513: Failed, 1 search nodes.
E=2 N=22 M=16512: OK, 40 tree nodes, 4 leaf nodes (0 safe).
E=3 N=25 M=12777: Failed, 224 search nodes.
E=3 N=25 M=12776: OK, 100 tree nodes, 6 leaf nodes (0 safe).
E=4 N=28 M=11111: Failed, 1 search nodes.
E=4 N=28 M=11110: OK, 180 tree nodes, 9 leaf nodes (0 safe).
E=5 N=31 M=10406: OK, 297 tree nodes, 11 leaf nodes (0 safe).
E=6 N=34 M=10249: OK, 1369 tree nodes, 16 leaf nodes (0 safe).
E=7 N=37 M=10249: lift succeeded: 16 leaf nodes (0 safe).
E=8 N=40 M=10249: lift succeeded: 16 leaf nodes (0 safe).
E=9 N=43 M=10249: lift succeeded: 16 leaf nodes (0 safe).

E=10 N=46 M=10249: lift succeeded: 16 leaf nodes (5 safe).
E=11 N=49 M=10249: lift succeeded: 16 leaf nodes (13 safe).
E=12 N=52 M=10249: lift succeeded: 16 leaf nodes (16 safe).
E=1 N=20 M=49932: OK, 33 tree nodes, 3 leaf nodes (0 safe).
E=2 N=23 M=30283: Failed, 1 search nodes.
E=2 N=23 M=30282: OK, 67 tree nodes, 5 leaf nodes (0 safe).
E=3 N=26 M=22733: Failed, 1 search nodes.
E=3 N=26 M=22732: OK, 101 tree nodes, 6 leaf nodes (0 safe).
E=4 N=29 M=19283: Failed, 1 search nodes.
E=4 N=29 M=19282: OK, 219 tree nodes, 9 leaf nodes (0 safe).
E=5 N=32 M=17687: Failed, 1 search nodes.
E=5 N=32 M=17686: OK, 359 tree nodes, 10 leaf nodes (0 safe).
E=6 N=35 M=17117: Failed, 1 search nodes.
E=6 N=35 M=17116: OK, 557 tree nodes, 14 leaf nodes (0 safe).
E=7 N=38 M=17116: lift succeeded: 14 leaf nodes (0 safe).
E=8 N=41 M=17116: lift succeeded: 14 leaf nodes (0 safe).
E=9 N=44 M=17116: lift failed.
E=7 N=38 M=17117: Failed, 1 search nodes.
E=7 N=38 M=17116: OK, 572 tree nodes, 21 leaf nodes (0 safe).
E=8 N=41 M=17116: lift succeeded: 21 leaf nodes (0 safe).
E=9 N=44 M=17116: lift failed.
E=8 N=41 M=17117: Failed, 1 search nodes.
E=8 N=41 M=17116: OK, 572 tree nodes, 21 leaf nodes (0 safe).
E=9 N=44 M=17116: lift failed.
E=9 N=44 M=17117: Failed, 1 search nodes.
E=9 N=44 M=17116: OK, 676 tree nodes, 21 leaf nodes (0 safe).
E=10 N=47 M=17116: lift succeeded: 21 leaf nodes (0 safe).
E=11 N=50 M=17116: lift succeeded: 21 leaf nodes (8 safe).
E=12 N=53 M=17116: lift succeeded: 21 leaf nodes (17 safe).
E=13 N=56 M=17116: lift succeeded: 21 leaf nodes (21 safe).
E=1 N=21 M=95325: Failed, 1 search nodes.
E=1 N=21 M=95324: OK, 35 tree nodes, 3 leaf nodes (0 safe).

E=2 N=24 M=55738: OK, 68 tree nodes, 5 leaf nodes (0 safe).
E=3 N=27 M=40622: OK, 131 tree nodes, 6 leaf nodes (0 safe).
E=4 N=30 M=33626: OK, 206 tree nodes, 7 leaf nodes (0 safe).
E=5 N=33 M=30217: Failed, 1 search nodes.
E=5 N=33 M=30216: OK, 345 tree nodes, 10 leaf nodes (0 safe).
E=6 N=36 M=28734: OK, 706 tree nodes, 13 leaf nodes (0 safe).
E=7 N=39 M=28467: OK, 4410 tree nodes, 19 leaf nodes (0 safe).
E=8 N=42 M=28467: lift succeeded: 19 leaf nodes (0 safe).
E=9 N=45 M=28467: lift succeeded: 19 leaf nodes (0 safe).
E=10 N=48 M=28467: lift succeeded: 19 leaf nodes (0 safe).
E=11 N=51 M=28467: lift succeeded: 19 leaf nodes (1 safe).
E=12 N=54 M=28467: lift succeeded: 19 leaf nodes (11 safe).
E=13 N=57 M=28467: lift succeeded: 19 leaf nodes (17 safe).
E=14 N=60 M=28467: lift succeeded: 19 leaf nodes (19 safe).
E=1 N=22 M=182361: Failed, 1 search nodes.
E=1 N=22 M=182360: OK, 36 tree nodes, 3 leaf nodes (0 safe).
E=2 N=25 M=102927: Failed, 1 search nodes.
E=2 N=25 M=102926: OK, 70 tree nodes, 5 leaf nodes (0 safe).
E=3 N=28 M=72885: Failed, 1 search nodes.
E=3 N=28 M=72884: OK, 113 tree nodes, 5 leaf nodes (0 safe).
E=4 N=31 M=58904: OK, 206 tree nodes, 7 leaf nodes (0 safe).
E=5 N=34 M=51869: Failed, 1 search nodes.
E=5 N=34 M=51868: OK, 404 tree nodes, 10 leaf nodes (0 safe).
E=6 N=37 M=48475: Failed, 2212 search nodes.
E=6 N=37 M=48474: OK, 584 tree nodes, 13 leaf nodes (0 safe).
E=7 N=40 M=47307: Failed, 1 search nodes.
E=7 N=40 M=47306: OK, 1071 tree nodes, 16 leaf nodes (0 safe).
E=8 N=43 M=47306: lift succeeded: 16 leaf nodes (0 safe).
E=9 N=46 M=47306: lift succeeded: 16 leaf nodes (0 safe).

E=10 N=49 M=47306: lift failed.
E=8 N=43 M=47307: Failed, 1 search nodes.
E=8 N=43 M=47306: OK, 1071 tree nodes, 16 leaf nodes (0 safe).
E=9 N=46 M=47306: lift succeeded: 16 leaf nodes (0 safe).
E=10 N=49 M=47306: lift failed.
E=9 N=46 M=47307: Failed, 1 search nodes.
E=9 N=46 M=47306: OK, 1071 tree nodes, 16 leaf nodes (0 safe).
E=10 N=49 M=47306: lift failed.
E=10 N=49 M=47307: Failed, 1 search nodes.
E=10 N=49 M=47306: OK, 1574 tree nodes, 16 leaf nodes (0 safe).
E=11 N=52 M=47306: lift succeeded: 16 leaf nodes (0 safe).
E=12 N=55 M=47306: lift succeeded: 16 leaf nodes (4 safe).
E=13 N=58 M=47306: lift succeeded: 16 leaf nodes (12 safe).
E=14 N=61 M=47306: lift succeeded: 16 leaf nodes (16 safe).
E=1 N=23 M=349525: Failed, 1 search nodes.
E=1 N=23 M=349524: OK, 39 tree nodes, 3 leaf nodes (0 safe).
E=2 N=26 M=190650: OK, 77 tree nodes, 5 leaf nodes (0 safe).
E=3 N=29 M=131264: OK, 105 tree nodes, 6 leaf nodes (0 safe).
E=4 N=32 M=103620: OK, 214 tree nodes, 7 leaf nodes (0 safe).
E=5 N=35 M=89439: Failed, 1 search nodes.
E=5 N=35 M=89438: OK, 494 tree nodes, 10 leaf nodes (0 safe).
E=6 N=38 M=82160: OK, 605 tree nodes, 12 leaf nodes (0 safe).
E=7 N=41 M=78986: OK, 1336 tree nodes, 15 leaf nodes (0 safe).
E=8 N=44 M=78589: OK, 10920 tree nodes, 23 leaf nodes (0 safe).
E=9 N=47 M=78589: lift succeeded: 23 leaf nodes (0 safe).
E=10 N=50 M=78589: lift failed.
E=9 N=47 M=78589: OK, 10920 tree nodes, 23 leaf nodes (0 safe).
E=10 N=50 M=78589: lift failed.

E=11 N=53 M=78589: lift succeeded: 23 leaf nodes (0 safe).
E=12 N=56 M=78589: lift succeeded: 23 leaf nodes (0 safe).
E=13 N=59 M=78589: lift succeeded: 23 leaf nodes (8 safe).
E=14 N=62 M=78589: lift succeeded: 23 leaf nodes (18 safe).
E=15 N=65 M=78589: lift succeeded: 23 leaf nodes (23 safe).
E=1 N=24 M=671088: OK, 39 tree nodes, 3 leaf nodes (0 safe).
E=2 N=27 M=354136: OK, 76 tree nodes, 5 leaf nodes (0 safe).
E=3 N=30 M=237238: OK, 124 tree nodes, 6 leaf nodes (0 safe).
E=4 N=33 M=183005: OK, 434 tree nodes, 8 leaf nodes (0 safe).
E=5 N=36 M=154876: OK, 361 tree nodes, 10 leaf nodes (0 safe).
E=6 N=39 M=139867: Failed, 1 search nodes.
E=6 N=39 M=139866: OK, 812 tree nodes, 11 leaf nodes (0 safe).
E=7 N=42 M=132474: OK, 1135 tree nodes, 14 leaf nodes (0 safe).
E=8 N=45 M=130088: OK, 2050 tree nodes, 20 leaf nodes (0 safe).
E=9 N=48 M=130088: lift succeeded: 20 leaf nodes (0 safe).
E=10 N=51 M=130088: lift succeeded: 20 leaf nodes (0 safe).
E=11 N=54 M=130088: lift failed.
E=9 N=48 M=130088: OK, 2060 tree nodes, 28 leaf nodes (0 safe).
E=10 N=51 M=130088: lift succeeded: 28 leaf nodes (0 safe).
E=11 N=54 M=130088: lift failed.
E=10 N=51 M=130088: OK, 2060 tree nodes, 28 leaf nodes (0 safe).
E=11 N=54 M=130088: lift failed.
E=11 N=54 M=130088: OK, 3013 tree nodes, 28 leaf nodes (0 safe).
E=12 N=57 M=130088: lift succeeded: 28 leaf nodes (0 safe).
E=13 N=60 M=130088: lift succeeded: 28 leaf nodes (3 safe).
E=14 N=63 M=130088: lift succeeded: 28 leaf nodes (13 safe).
E=15 N=66 M=130088: lift succeeded: 28 leaf nodes (21 safe).
E=16 N=69 M=130088: lift succeeded: 28 leaf nodes (26 safe).
E=17 N=72 M=130088: lift succeeded: 28 leaf nodes (28 safe).
E=1 N=25 M=1290555: Failed, 1 search nodes.

E=1 N=25 M=1290554: OK, 44 tree nodes, 3 leaf nodes (0 safe).
E=2 N=28 M=659546: OK, 82 tree nodes, 5 leaf nodes (0 safe).
E=3 N=31 M=430185: Failed, 1 search nodes.
E=3 N=31 M=430184: OK, 129 tree nodes, 6 leaf nodes (0 safe).
E=4 N=34 M=324417: Failed, 558 search nodes.
E=4 N=34 M=324416: OK, 224 tree nodes, 8 leaf nodes (0 safe).
E=5 N=37 M=269268: OK, 457 tree nodes, 10 leaf nodes (0 safe).
E=6 N=40 M=239103: Failed, 1 search nodes.
E=6 N=40 M=239102: OK, 868 tree nodes, 11 leaf nodes (0 safe).
E=7 N=43 M=223138: OK, 1236 tree nodes, 14 leaf nodes (0 safe).
E=8 N=46 M=216269: OK, 8760 tree nodes, 17 leaf nodes (0 safe).
E=9 N=49 M=215900: OK, 18900 tree nodes, 30 leaf nodes (0 safe).
E=10 N=52 M=215900: lift succeeded: 30 leaf nodes (0 safe).
E=11 N=55 M=215900: lift failed.
E=10 N=52 M=215900: OK, 18900 tree nodes, 30 leaf nodes (0 safe).
E=11 N=55 M=215900: lift failed.
E=11 N=55 M=215900: OK, 34232 tree nodes, 30 leaf nodes (0 safe).
E=12 N=58 M=215900: lift succeeded: 30 leaf nodes (0 safe).
E=13 N=61 M=215900: lift succeeded: 30 leaf nodes (0 safe).
E=14 N=64 M=215900: lift succeeded: 30 leaf nodes (6 safe).
E=15 N=67 M=215900: lift succeeded: 30 leaf nodes (18 safe).
E=16 N=70 M=215900: lift succeeded: 30 leaf nodes (26 safe).
E=17 N=73 M=215900: lift succeeded: 30 leaf nodes (30 safe).
E=1 N=26 M=2485513: Failed, 1 search nodes.
E=1 N=26 M=2485512: OK, 44 tree nodes, 3 leaf nodes (0 safe).
E=2 N=29 M=1231355: Failed, 1 search nodes.
E=2 N=29 M=1231354: OK, 79 tree nodes, 5 leaf nodes (0 safe).

E=4 N=35 M=577125: Failed, 1 search nodes.
E=4 N=35 M=577124: OK, 241 tree nodes, 8 leaf nodes (0 safe).
E=5 N=38 M=469928: OK, 409 tree nodes, 10 leaf nodes (0 safe).
E=6 N=41 M=410374: OK, 893 tree nodes, 12 leaf nodes (0 safe).
E=7 N=44 M=377388: OK, 1554 tree nodes, 15 leaf nodes (0 safe).
E=8 N=47 M=361035: Failed, 1 search nodes.
E=8 N=47 M=361034: OK, 2285 tree nodes, 18 leaf nodes (0 safe).
E=9 N=50 M=356245: OK, 15868 tree nodes, 26 leaf nodes (0 safe).
E=10 N=53 M=356245: lift failed.
E=10 N=53 M=356245: OK, 15908 tree nodes, 38 leaf nodes (0 safe).
E=11 N=56 M=356245: lift succeeded: 38 leaf nodes (0 safe).
E=12 N=59 M=356245: lift failed.
E=11 N=56 M=356245: OK, 15908 tree nodes, 38 leaf nodes (0 safe).
E=12 N=59 M=356245: lift failed.
E=12 N=59 M=356245: OK, 23370 tree nodes, 38 leaf nodes (0 safe).
E=13 N=62 M=356245: lift succeeded: 38 leaf nodes (0 safe).
E=14 N=65 M=356245: lift succeeded: 38 leaf nodes (1 safe).
E=15 N=68 M=356245: lift succeeded: 38 leaf nodes (12 safe).
E=16 N=71 M=356245: lift succeeded: 38 leaf nodes (25 safe).
E=17 N=74 M=356245: lift succeeded: 38 leaf nodes (34 safe).
E=18 N=77 M=356245: lift succeeded: 38 leaf nodes (38 safe).
E=1 N=27 M=4793490: OK, 48 tree nodes, 3 leaf nodes (0 safe).
E=2 N=30 M=2304167: Failed, 1 search nodes.
E=2 N=30 M=2304166: OK, 92 tree nodes, 5 leaf nodes (0 safe).
E=3 N=33 M=1427373: Failed, 1 search nodes.
E=3 N=33 M=1427372: OK, 150 tree nodes, 6 leaf nodes (0 safe).
E=4 N=36 M=1030091: Failed, 1 search nodes.
E=4 N=36 M=1030090: OK, 294 tree nodes, 8 leaf nodes (0 safe).

E=6 N=42 M=706994: OK, 1134 tree nodes, 12 leaf nodes (0 safe).
E=7 N=45 M=640756: OK, 1380 tree nodes, 15 leaf nodes (0 safe).
E=8 N=48 M=605094: OK, 2386 tree nodes, 18 leaf nodes (0 safe).
E=9 N=51 M=590174: OK, 4145 tree nodes, 23 leaf nodes (0 safe).
E=10 N=54 M=590174: lift failed.
E=10 N=54 M=590174: OK, 4034 tree nodes, 36 leaf nodes (0 safe).
E=11 N=57 M=590174: lift succeeded: 36 leaf nodes (0 safe).
E=12 N=60 M=590174: lift failed.
E=11 N=57 M=590174: OK, 4034 tree nodes, 36 leaf nodes (0 safe).
E=12 N=60 M=590174: lift failed.
E=12 N=60 M=590174: OK, 8544 tree nodes, 36 leaf nodes (0 safe).
E=13 N=63 M=590174: lift succeeded: 36 leaf nodes (0 safe).
E=14 N=66 M=590174: lift failed.
E=13 N=63 M=590174: OK, 9471 tree nodes, 36 leaf nodes (0 safe).
E=14 N=66 M=590174: lift failed.
E=14 N=66 M=590174: OK, 11852 tree nodes, 36 leaf nodes (0 safe).
E=15 N=69 M=590174: lift succeeded: 36 leaf nodes (5 safe).
E=16 N=72 M=590174: lift succeeded: 36 leaf nodes (19 safe).
E=17 N=75 M=590174: lift succeeded: 36 leaf nodes (29 safe).
E=18 N=78 M=590174: lift succeeded: 36 leaf nodes (34 safe).
E=19 N=81 M=590174: lift succeeded: 36 leaf nodes (36 safe).
E=1 N=28 M=9256395: Failed, 1 search nodes.
E=1 N=28 M=9256394: OK, 50 tree nodes, 3 leaf nodes (0 safe).
E=2 N=31 M=4320892: OK, 94 tree nodes, 5 leaf nodes (0 safe).
E=3 N=34 M=2610922: OK, 161 tree nodes, 6 leaf nodes (0 safe).
E=4 N=37 M=1844347: Failed, 532 search nodes.
E=4 N=37 M=1844346: OK, 297 tree nodes, 8 leaf nodes (0 safe).
E=5 N=40 M=1446537: Failed, 1 search nodes.

E=5 N=40 M=1446536: OK, 444 tree nodes, 9 leaf nodes (0 safe).
E=6 N=43 M=1222401: Failed, 1 search nodes.
E=6 N=43 M=1222400: OK, 699 tree nodes, 12 leaf nodes (0 safe).
E=7 N=46 M=1091975: Failed, 1 search nodes.
E=7 N=46 M=1091974: OK, 1860 tree nodes, 15 leaf nodes (0 safe).
E=8 N=49 M=1017991: Failed, 1 search nodes.
E=8 N=49 M=1017990: OK, 2301 tree nodes, 18 leaf nodes (0 safe).
E=9 N=52 M=981465: Failed, 1 search nodes.
E=9 N=52 M=981464: OK, 4444 tree nodes, 23 leaf nodes (0 safe).
E=10 N=55 M=972164: OK, 14922 tree nodes, 33 leaf nodes (0 safe).
E=11 N=58 M=972164: lift succeeded: 33 leaf nodes (0 safe).
E=12 N=61 M=972164: lift failed.
E=11 N=58 M=972164: OK, 14930 tree nodes, 47 leaf nodes (0 safe).
E=12 N=61 M=972164: lift failed.
E=12 N=61 M=972164: OK, 16684 tree nodes, 47 leaf nodes (0 safe).
E=13 N=64 M=972164: lift failed.
E=13 N=64 M=972164: OK, 22001 tree nodes, 47 leaf nodes (0 safe).
E=14 N=67 M=972164: lift succeeded: 47 leaf nodes (0 safe).
E=15 N=70 M=972164: lift failed.
E=14 N=67 M=972164: OK, 19902 tree nodes, 47 leaf nodes (0 safe).
E=15 N=70 M=972164: lift succeeded: 47 leaf nodes (0 safe).
E=16 N=73 M=972164: lift succeeded: 47 leaf nodes (10 safe).
E=17 N=76 M=972164: lift succeeded: 47 leaf nodes (26 safe).
E=18 N=79 M=972164: lift succeeded: 47 leaf nodes (37 safe).
E=19 N=82 M=972164: lift succeeded: 47 leaf nodes (44 safe).
E=20 N=85 M=972164: lift succeeded: 47 leaf nodes (47 safe).

Bibliography

[Balakirsky] Vladimir B. Balakirsky, A Direct Approach to Searching with Lies, submitted to Discrete Mathematics. Author is currently with Fakultät für Mathematik, Universität Bielefeld, Postfach 100131, D-33501 Bielefeld 1, Germany, submitted

[Berlekamp] Elwyn R. Berlekamp, Block Coding with Noiseless Feedback, doctoral dissertation, Massachusetts Institute of Technology, 1964.

[Berlekamp2] Elwyn R. Berlekamp, Block Coding for the Binary Symmetric Channel with Noiseless, Delayless Feedback in Error Correcting Codes, Proceedings of a Symposium Conducted by the Mathematics Research Center, United States Army at the University of Wisconsin, Madison, edited by Henry B. Mann, John Wiley & Sons, Inc. (May 6–8, 1968), pp. 61–88.

[Cesa-Bianchi] Nicoló Cesa-Bianchi, Yoav Freund, David P. Helmbold, and Manfred K. Warmuth, On-line Prediction and Conversion Strategies in Machine Learning 25, Kluwer Academic Publishers, Boston (1996), pp. 71–110.

[Czyzowicz] Jurek Czyzowicz, Daniele Mundici, and Andrezej Pelc, Ulam’s Searching Game with Lies in Journal of Combinatorial Theory, Series A 52 (1989), pp. 62–76.

[Deppe] Christian Deppe, Solution of Ulam’s Searching Game with Three Lies or an Optimal Adaptive Strategy for Binary Three-Error-Correcting-Codes, doctoral dissertation, Universität Bielefeld, 1998.

[Hill] Ray Hill, Searching with Lies, Department of Mathematics & Computer Science, University of Salford, Salford M5 4WT, England.

[Hill2] Ray Hill, J. P. Karim, and Elwyn R. Berlekamp, The Solution of a problem of Ulam on searching with lies.

[Hill3] Ray Hill, J. P. Karim, and Elwyn R. Berlekamp, The Solution of a problem of Ulam on searching with lies.

[Karp] Richard M. Karp, ISIT’98 Plenary Lecture Report: Variations on the Theme of ‘Twenty Questions’ in IEEE Information Theory Society Newsletter 49 No. 1, edited by Kimberly Wasserman, March 1999, pp. 1–5, 21–22.

[Lawler] Eugene L. Lawler and Sergei Sarkissian, An algorithm for “Ulam’s Game” and its application to error correcting codes in Information Processing Letters 56, Elsevier (1995), pp. 89-93.

[Pelc] Andrzej Pelc, Solution of Ulam’s Problem on Searching with a Lie in Journal of Combinatorial Theory, Series A 44 (1987), pp. 129–140.

[Piccione] Michele Piccione and Ariel Rubinstein, On the Interpretation of Decision Problems with Imperfect Recall, in Games and Economic Behavior 20, Article No. GA970536, (1997), pp. 3–24.

[Spencer] Joel Spencer, Ulam’s searching game with a fixed number of lies in Theoretical Computer Science 95, Elsevier (1992), pp. 307–321.

[Spencer2] Joel Spencer, Randomization, derandomization and antirandomization: three games in Theoretical Computer Science 131, Elsevier (1994), pp. 415–429.

[Ulam] Adventures of a Mathematician, University of California Press, Berkeley, CA, 1992.