Lester Hill’s “The checking of the accuracy …”, part 14

Backstory: Lester Saunders Hill wrote unpublished notes, about 40 pages long, probably in the mid- to late 1920s. They were titled “The checking of the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields”. In the 1960s this manuscript was given to David Kahn by Hill’s widow. The notes were typewritten, but mathematical symbols, tables, insertions, and some footnotes were often handwritten. I thank Chris Christensen, the National Cryptologic Museum, and NSA’s David Kahn Collection, for their help in obtaining these notes. Many thanks also to Rene Stein of the NSA Cryptologic Museum library and David Kahn for permission to publish this transcription. Comments by transcriber will look like this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the 15th section of his paper. I hope to post more later. (Part 14 is here.)


 

Lemma concerning reference matrices

The general reference matrix of Section 3 was:

Q =   \left(  \begin{array}{cccc}  k_{11} & k_{12} &  \dots & k_{1n} \\  k_{21} & k_{22} &  \dots & k_{2n} \\  \vdots & & & \vdots \\  k_{q1} & k_{q2} &  \dots & k_{qn} \\  \end{array}  \right)
the k_{ij} being elements of any given finite algebraic field F, and q being less than or equal to n.

This matrix contains determinants of order r with r=1,2,\dots, q — determinants of first order (r=1) being single elements of the matrix.

We recall that if f_1, f_2, \dots, f_{s} is an s element operand
sequence in F, a t-element check based upon the matrix Q is:

c_j = \sum_{i=1}^{s} k_{ji} f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, t).
it being understood that s\leq n, t\leq q.

Let Q contain no vanishing determinant of any order: Let c_1, c_2, \dots, c_{t} be a t-element check, t\leq q, on the operand sequence f_1, f_2, \dots, $f_{s}$, $s\leq n$. Let v be a positive integer less than or equal to s+t. If, in the transmittal of the sequence

f_1, f_2, \dots, f_{s}, c_1, c_2, \dots, c_{t},
errors occur in v of its s+t elements, whatever the distribution of the errors, the presence of error will certainly be disclosed, or will enjoy only a 1-in-(\Gamma-1)^t chance of escaping disclosure, according as $v$ is, or is not, less than t+1. In this statement, \Gamma denotes the total number of elements in the field F.

proof:
Case 1:
Let all v errors fall among the c_1, c_2, \dots, c_{t}. The presence of error is evidently certain to be disclosed.

Case 2:
Let all v errors fall among the $f_1, f_2, \dots, f_{s}$.

(2.1): Let v\leq t. There is no loss of generality of we assume [This assumption implies v\leq s. – wdj] the $v$ errors are \epsilon_1, \epsilon_2, \dots, \epsilon_v, affecting f_1, f_2, \dots, f_{v}. The errors cannot escape disclosure. For, to do so, they would have to satisfy the system of homogeneous linear equations:

\sum_{i=1}^{v} k_{ji} \epsilon_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, t).
in which the matrix of coefficients k_{ji} contains no vanishing determinant of any order, and which, therefore admits no solution other than \epsilon_i=0 (i = 1, 2, \dots, v).

For this treatment of the errors, compare Sections 4, 5.

Case 3:
Let z errors fall among the f_i and w=v-z errors fall among the c_j. Without loss in generality, we may assume that the errors are \epsilon_1, \epsilon_2, \dots, \epsilon_z, affecting f_1, f_2, \dots, f_{z}, and \delta_{j_1}, \delta_{j_2}, \dots, \delta_{j_w}, affecting c_{j_1}, c_{j_2}, \dots, c_{j_w}.

(3.1): Let z+w\leq t. Writing t=v+h=z+w+h, where h denotes a non-negative integer which may or may not be zero, we have t-w = z+h. Hence z+h of the c_j are transmitted without error.

If the presence of error is to escape disclosure, we see, therefore, that the z errors $\epsilon_i$ must satisfy the system of at least z homogeneous linear equations:

\sum_{i=1}^{z} k_{r_m,i} \epsilon_i,\ \ \ \ \ \ \ (m = 1, 2, \dots, z+h),
where the indices r_m denote a set of z+h integers selected from 1, 2, \dots, t. But the matrix of coefficients in this system contains no vanishing determinant, so that the only solution would be \epsilon_i=0 (i = 1, 2, \dots, z).

For details in this treatment of errors, see Section \ref{sec:5}.

(3.2): Let z+w> t. Then w = t-(z-h), where $h$ denotes a positive integer. Assuming that the presence of error is to escape detection, we see, therefore, that the v errors must satisfy t linear equations as follows:

(\alpha) a system of z-h equations involving only the errors \epsilon_i, (i = 1, 2, \dots, z), and homogeneous in these $z$ errors;

(\beta) a system of w equations involving all v errors.

Since the matrix of the coefficients in the system (\alpha) contains no vanishing determinant, we can solve this system for $z-h$ of the $\epsilon_i$ as rational functions of the remaining h of the \epsilon_i.

The system (\beta) determines all errors affecting the c_j — that is, all the errors \delta_{j_i} — as polynomial functions of the \epsilon_i, (i = 1, 2, \dots, z).

Hence, all told, (z-h)+w errors are determined as rational functions of the remaining h errors. In other words, v-t errors determine the other $t$ errors.

An accidental error can assume any one of $\Gamma -1$ values, there being \Gamma elements in the finite field F. Hence the chance that the errors will check up, and thus escape disclosure, is only 1-in-(\Gamma-1)^t.
QED

Searching with lies, 1

In Stanislaw Ulam’s 1976 autobiography (Adventures of a mathematician, Scribner and Sons, New York, 1976), one finds the following problem concerning two players playing a generalization of the childhood game of “20 questions”.
(As a footnote: the history of who invented this game is unclear. It occurred in writings of Renyi, for example “On a problem in information theory” (Hungarian), Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961)505–516, but may have been known earlier under the name “Bar-kochba”.)

Problem: Player 1 secretly chooses a number from 1 to M (M is large but fixed, say M = 1000000). Player 2 asks a series of “yes/no questions” in an attempt to determine that number. Player 1 can lie at most e times (e\geq 0 is fixed). Assuming best possible play on both sides, what is the minimum number of “yes/no questions” Player 2 must ask to (in general) be able to correctly determine the number Player 1 selected?

There is a very large literature on this problem. Just google “searching with lies” (with the quotes) to see a selection of the papers (eg, this paper). It turns out this children’s game, when suitably generalized, has numerous applications to computer science and engineering.

We start with a simple example. Pick an integer from 0 to 1000000. For example, suppose you pick 2^{19}+1 = 524289.

Here is how I can ask you 20 True/False questions and guess your number.

Is your number less than 524288? False

Is your number less than 655360? True
Is your number less than 589824? True

Is your number less than 557056? True
Is your number less than 540672? True
Is your number less than 532480? True
Is your number less than 528384? True
Is your number less than 526336? True
Is your number less than 525312? True
Is your number less than 524800? True
Is your number less than 524544? True
Is your number less than 524416? True
Is your number less than 524352? True
Is your number less than 524320? True
Is your number less than 524304? True
Is your number less than 524296? True
Is your number less than 524292? True
Is your number less than 524290? True
Is your number less than 524289? False

This is the general description of the binary search strategy:
First, divide the whole interval of size 2^{20} into half and find which half the number lies in. Discard the one it does not lie in.
Second, divide the subinterval of size 2^{19} into half and find which half the number lies in. Discard the one it does not lie in.
Third, divide the subinterval of size 2^{18} into half and find which half the number lies in. Discard the one it does not lie in.
And so on.
This process must stop after 20 steps, as you run out of non-trivial subintervals.

This is an instance of “searching with lies” where no lies are told and “feedback” is allowed.

Another method:
I don’t know what your number is, but whatever it is, represent it in binary as a vector

b = (b_0, b_1, ..., b_N)\ \  {\rm so}\ \  M = b_02^0 + b_12^1 + ... + b_N2^N,

where N = ceiling(\log_2(N))=20, where 2^{20}-1 = 1048574. The 20 questions are:
Is b_0 = 0?
Is b_1 = 0?
and so on
Is b_N = 0?
You may determine the value of the b_i‘s from this (since each b_i is either 0 or 1).

This is an instance of “searching with lies” where no lies are told and “feedback” is not allowed.

Let’s go back to our problem where Player 1 secretly chooses a number from 1 to M (M is large but fixed, say M = 1000000). Use the following notation: If the answers between successive questions is possible and then questions may be adapted to these answers (“feedback allowed”), call this minimum number of “yes/no questions” Player 2 must ask, f(M,e). If feedback is not allowed, call this minimum number g(M,e).

Clearly, f(M,e)\leq g(M,e).

In practice, we not only want to know f(M,e) (resp., g(M,e) but an efficient algorithm for determining the “yes/no questions” Player 2 should ask.

In his 1964 PhD thesis (E. Berlekamp, Block coding with noiseless feedback, PhD Thesis, Dept EE, MIT, 1964), Berlekamp was concerned with a discrete analog of a problem which arises when trying to design a analog-to-digital converter for sound recording which compensates for possible feedback.

To formulate this problem in the case when lies are possible, we introduce some new terms.

Definitions

A binary code is a set C of n-tuples of 0‘s and 1‘s, i.e., a subset C\subset GF(2)^n, where GF(2)={\bf Z}/2{\bf Z}=\{0,1\} is the field of integers \pmod{2}. If we assume, in addition, C is a vector space over GF(2) then we say C is a linear binary code. A codeword is an element of a binary code.
The Hamming distance between n-tuples w,w'\in GF(2)^n is the number d(w,w') of non-zero coordinates of w-w'.
The minimum distance of C is the smallest integer d such that d(c,c')\geq d for all distinct c,c'\in C.

For example, let

C = \{ (0, 0, 0), (1, 1, 1) \} \subset GF(2)^2.

This is a 1-error correcting code of minimum distance d=3.

We say that C is e-error correcting if the following property always holds: given any w\in GF(2)^n and any c\in C, if d(w,c)\leq e then every c'\in C, c\not= c', must satisfy d(w,c')\ge e (in other words, there is at most one codeword within distance e from any w\in GF(2)^n).

Let A(n,d) denote the largest possible size of a binary code C\subset GF(2)^n of minimum distance d.

Fact: If a binary code C\subset GF(2)^n is e-error correcting then |C|\leq A(n,2e+1).

Let B(n,d) denote the largest possible size of a binary linear code C\subset GF(2)^n of minimum distance d. It is known that B(n,d)=2^k, for some k (called the dimension of C).

Clearly, A(n,d)\leq B(n,d).

A Reduction

Fact: Fix any e and M. g(M,e) is the smallest n such that A(n,2e+1)\geq M.

Record the n answers to all the “yes/no questions” as an n-tuple of 0‘s (for “no”) and 1‘s (for “yes”). The binary code C is the set of all codewords corresponding to correct answers. Intuitively, if you are Player 2 and you ask Player 1 what the coordinates of his codeword c associated to his secret number is, and if he lies e times then you will receive from him a binary vector w of Hamming distance e from a codeword. Since C is e-error correcting, you can determine c from w.

We want the smallest possible n satisfying the condition A(n,2e+1)\geq M. The values of B(n,2e+1) (or \log_2 B(n, d), where we take d=2e+1, to be more precise) have been tabulated for “small” values of M and e online at the MinT website (U. of Salzburg, Wolfgang Ch. Schmid and Rudolf Schürer), codetables.de (Markus Grassl), and Boston U. (Ari Trachtenberg). This gives us an upper bound for g(M,e), and hence also for f(M,e) for “small” values of M and e.

Here’s a recipe for using online tables to find a good upper bound the smallest number Q of questions Player 2 must ask Player 1, if Player 1 gets to lie e times:

  • Find the smallest k such that 2^k \geq M,
  • go to the table minT and go to the row d=2e+1; find the smallest column number n which contains an entry greater than or equal to k.
  • that column number n is an upper bound for Q.