Searching with lies, 2

Posted on 2012/06/20 by wdjoyner

In the previous post, we have seen how the number of questions needed to determine the number selected in the non-adaptive/”no feedback” situation is closely connected with the construction of “best possible” error-correcting codes. Let us look at some tables of specific values.

Odd $M\leq 50$ :

$\begin{array}{|c|c|c|} M & f(M,1) & g(M,1) \\ \hline 11& 7& 7\\ 13& 7& 7\\ 15& 7& 7\\ 17& 8& 9\\ 19& 8& 9\\ 21& 8& 9\\ 23& 8& 9\\ 25& 8& 9\\ 27& 8& 9\\ 29& 9& 9\\ 31& 9& 9\\ 33& 9& 9\\ 35& 9& 10\\ 37& 9& 10\\ 39& 9& 10\\ 41& 9& 10\\ 43& 9& 10\\ 45& 9& 10\\ 47& 9& 10\\ 49& 9& 10\\ \hline \end{array}$

Even $M\leq 50$ :

$\begin{array}{|c|c|c|} M & f(M,1) & g(M,1) \\ \hline 10& 7& 7\\ 12& 7& 7\\ 14& 7& 7\\ 16& 7& 7\\ 18& 8& 9\\ 20& 8& 9\\ 22& 8& 9\\ 24& 8& 9\\ 26& 8& 9\\ 28& 8& 9\\ 30& 9& 9\\ 32& 9& 9\\ 34& 9& 10\\ 36& 9& 10\\ 38& 9& 10\\ 40& 9& 10\\ 42& 9& 10\\ 44& 9& 10\\ 46& 9& 10\\ 48& 9& 10\\ 50& 9& 10\\ \hline \end{array}$

Next, we tabulate some values of $f(10^6, e)$ for different values of $e\geq 0$ (see R. Hill, J. Karim, E. Berlekamp, “The solution of a problem of Ulam on searching with lies,” IEEE, 1998):

$\begin{array}{|c|c|} e & f(M,e) \\ \hline 0 & 20 \\ 1 & 25 \\ 2 & 29 \\ 3 & 33 \\ 4 & 37 \\ 5 & 40 \\ 6 & 43 \\ 7 & 46 \\ 8 & 50 \\ 9 & 53 \\ \vdots & \vdots \\ e & 3e+26 \\ \hline \end{array}$

What is remarkable, I think, is that even if you are allowed to modify your questions adaptively, depending on the answer given, it won’t help you very much.

Searching with lies, 1

Posted on 2012/06/19 by wdjoyner

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.

Lester Hill and error-detecting codes screencast

Posted on 2012/06/11 by wdjoyner

Lester Saunders Hill (1890-1961) is famous for having discovered the Hill cryptosystem (en.wikipedia.org/wiki/Hill_cipher). It was recently discovered that Hill wrote an unpublished paper (undated but probably written in the 1920s) in which he discovered a class of error-correcting codes not found by others until decades later. This screencast is a non-technical exposition into the history of this side of Hill’s work.

Thanks to Chris Christensen, David Kahn, and Rene Stein (librarian for NSA Cryptologic Museum) for material on which this presentation is based. For more on the “message protector”, see http://www.nku.edu/~christensen/Cryptological%20History%20Symposium.pdf.

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

Posted on 2012/06/09 by wdjoyner

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 his this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the seventh section of his paper. I hope to post more later. (Part 6 is here.)

Section 7: The general form of reference matrix

Let $a_1, a_2, \dots a_n$ be $n$ different elements of our finite field $F$ , and let $a_i$ be different from the zero element of $F$ . Then we shall emply a reference matrix of the form

$Q = \left( \begin{array}{cccc} a_1 & a_2 & \dots & a_{n} \\ a_1^2 & a_2^2 & \dots & a_{n}^2 \\ \vdots & & & \vdots \\ a_1^q & a_2^q & \dots & a_{n}^q \\ \end{array} \right)$

or of the form

$Q' = \left( \begin{array}{cccc} 1 & 1 & \dots & 1 \\ a_1 & a_2 & \dots & a_{n} \\ a_1^2 & a_2^2 & \dots & a_{n}^2 \\ \vdots & & & \vdots \\ a_1^{q-1} & a_2^{q-1} & \dots & a_{n}^{q-1} \\ \end{array} \right) \, .$

The actual procedure involved, and the real equivalence for checking purposes, of $Q$ and $Q'$ , will presently be illustrated. We note here merely that each of the matrices $Q$ , $Q'$ is of index $q$ . Let us examine $Q'$ . A similar argument will be applicable to $Q$ .

Suppose, for argument, that $Q'$ contains a vanishing $q$ -rowed determinant. Without loss of generality, we suppose that it is

$Q' = \left| \begin{array}{cccc} 1 & 1 & \dots & 1 \\ a_1 & a_2 & \dots & a_{q} \\ a_1^2 & a_2^2 & \dots & a_{q}^2 \\ \vdots & & & \vdots \\ a_1^{q-1} & a_2^{q-1} & \dots & a_{q}^{q-1} \\ \end{array} \right| \, .$
Since this determinant is equal to zero, Lemma 4 guarantees the existence, in our field $F$ , of the elements

$\lambda_1, \lambda_2, \dots \lambda_q,$

not all equal to zero, for which we may write

$\lambda_1 + \lambda_2 a_i +\lambda_3 a_i^2 + \dots + \lambda_q a_q^{q-1} = 0,$
( $i=1,2, \dots, q$ ). The $a_i$ being, as assumed, all different, this implies that the equation

$\lambda_1 + \lambda_2 x +\lambda_3 x^2 + \dots + \lambda_q x^{q-1} = 0,$

has $q$ different roots in $F$ , an implication which contradicts Lemma 5.

Thus $Q'$ contains no vanishing $q$ -rowed determinant, and if of index $q$ . In the same way, $Q$ may be shown to be of index $q$ . But unless these matrices are constructed with care, they will, of course, generally contain vanishing determinants of various orders less than $q$ . We defer for the moment the further consideration of this matter.

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

Posted on 2012/06/09 by wdjoyner

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. The manuscript is being LaTeXed “as we speak”. 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 his this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the sixth section of his paper. I hope to post more later. (Part 5 is here.)

Section 6: Arbitrary distrbution of errors affecting the $f_i$ and the $c_j$

It is highly desirable, although not strictly necessary, to fashion the reference matrix $Q$ in such a manner that every determinant contained in it, of every order, be different from zero.

Reference matrices of a practical type, and without a vanishing determinant of any order, may be construted in certain finite fields $F$ by very direct methods which can be more easily illustrated than described. It will be expedient at this poin, even at the expense of breaking the continuity of our discussion, to introduce concrete examples of operations in finite fields, and to show how reference matrices be conveniently set up in particular cases. The desirability of contriving that such matrices contain no vanishing determinant can then be brought out more effectively. The examination of arbitrary distributions of errors among the $n+q$ elements of a telegraphic sequence

$f_1, f_2, \dots, f_n, c_1, c_2, \dots, c_q$

can be deferred, therefore, until later.

But, before going into details, we will describe the general form of reference matrix to be employed in all cases.

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

Posted on 2012/06/09 by wdjoyner

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. The manuscript is being LaTeXed “as we speak”. 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 his this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the fifth section of his paper. I hope to post more later. (Part 4 is here.)

Section 5: The error distribution with at least $q$ errors $\epsilon_i$

Let the sequence (footnote: Arbitrary error distributions will be considered later. Cf. sections 15-18.)

$f_1, f_2, \dots, f_n,\ c_1, c_2, \dots, c_q$
be transmitted in the form

$f_1', f_2', \dots, f_n',\ c_1', c_2', \dots, c_q' \, ,$
containing $t\geq q$ errors which affect the $f_i$ , and $h\geq 0$ errors which affect the $c_j$ .

Let $t=q+s$ . Then, to avoid discussing again the case already considered, we assume that at least one of the two integers $s, h$
is greater than $0$ .

Let the errors among the $c_j$ be $\delta_{j_1}, \delta_{j_2}, \dots , \delta_{j_h}$ , affecting the $c_{j_1}, c_{j_2}, \dots , c_{j_h}$ . Without loss in generality, we may assume that the $t$ errors affecting the $f_i$ are $\epsilon_1, \epsilon_2, \dots, \epsilon_t$ , so that the first $t$ of the $f_i$ are transmitted in error.

Suppose that the mutilated sequence is in full check. Then:

$\sum_{i=1}^t k_{ji}(f_i+\epsilon_i)+\sum_{i=t+1}^n k_{ji}f_i =c_j+\delta_j$

$\sum_{i=1}^n k_{ji}f_i+\sum_{i=1}^t k_{ji}\epsilon_i =c_j+\delta_j$

whence

$\sum_{i=1}^t k_{ji}\epsilon_i=\delta_j$

where $j=1,2,\dots, q$ and where $\delta_j$ in $c_j$ and may, of course, be
equal to $0$ .

It follows that

$\sum_{i=1}^q k_{ji}\epsilon_i = \delta_j - \sum_{i=1}^t k_{ji}\epsilon_i = b_j = \phi_j(\epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_j),$
where $j=1,2,\dots, q$ and where $\phi_j$ denotes a polynomial in the errors $\epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_j$ .

The index of the reference matrix being $q$ , the determinant

$\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|$

of the systems of equations

$\sum_{i=1}^q k_{ji}\epsilon_i = b_j \ \ \ \ \ \ \ \ \ \ (j=1,2,\dots, q)$

is not zero. Hence if all the $b_j$ are equal to zero, Lemma 1 demands that all the $\epsilon_i$ , for $i=1, 2, \dots, q$ , be equal to zero, contrary to hypothesis.

If at least one of the $b_j$ is different from $0$ , Lemma 3 shows that $\epsilon_{1}, \epsilon_{2}, \dots , \epsilon_q$ are uniquely determined as functions of the $b_j$ , and therefore as functions of $\epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_1, \delta_2, \dots, \delta_q$ :

$\epsilon_i = \xi_i (\epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_1, \delta_2, \dots, \delta_q),\ \ \ \ \ \ \ \ \ \ (j=1,2,\dots, q)$

the functions $\xi_i$ being, of course, rational functions. But, by assumption, all of the $\delta_j$, except $\delta_{j_1}, \dots, \delta_{j_h}$ , vanish. Hence $\epsilon_i$ ( $i=1,2,\dots, q$ ) is a rational function of $\epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_{j_1}, \delta_{j_2}, \dots, \delta_{j_h}$ .

We conclude that if the mutilated message, containing $t+h$ errors, is to check up, so that the presence of error can escape detection, $q$ of the errors must be carefully adjusted as rational functions of the remaining $t+h-q$ errors.

It is easy to measure the chance that mere accidents of erroneous telegraphic transmittal might effect this adjustment. Let $\Gamma$ denote the total number of elements in the finite algebraic field $F$ which we are dealing. When an error is made in transmitting a sequence of elements of $F$ , the error may evidently have any one of $\Gamma -1$ values — an error with the value $0$ being no real error at all. It is therefore clear that our set of $t+h$ errors will enjoy only $1$ chance in $(\Gamma -1)^q$ of being accidentally adjusted so as to escape detection.

When $t=q+s$ errors occur among the $f_i$ and $h$ errors occur among the $c_j$ in the transmittal of the sequence $f_1, f_2, \dots, f_n,\ c_1, c_2, \dots, c_q$ , the errors being all of accidental telegraphic origin, the presence of error will infallibly be disclosed if $h=s=0$ ; and will enjoy a $1$ -in- $(\Gamma -1)^q$ of escaping disclosure if either of the two integers $h$ , $s$ is greater than $0$ .

This statement summarizes the results of the present section and those of section 4.

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

Posted on 2012/06/09 by wdjoyner

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. The manuscript is being LaTeXed “as we speak”. 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 his this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the fourth section of his paper. I hope to post more later. (Part 3 is here.)

Section 4: Index of the reference matrix $Q$

There will be considerable advantage in employing a reference matrix $Q$ of index $q$ .

Consider the sequence $f_1, f_2, \dots, f_n, c_1, c_2, \dots, c_q$ which is to be transmitted.
Errors may be made in transmittal, and the sequence may come through in the form

$f_1', f_2', \dots, f_n', c_1', c_2', \dots, c_q'\, ,$

where $f_i'=f_i+\epsilon_i$ , $c_j' = c_j + \delta_j$ , where $i = 1, 2, \dots, n$ , $j = 1, 2, \dots, q$ , the errors $\epsilon_i$ and $\delta_j$ being, of course, elements of the finite field $F$ . If $f_i$ (resp., $c_j$ ) is correctly transmitted then the error $\epsilon_i$ (resp., $c_j$ ) vanishes, and $f_i'=f_i$ (resp., $c_j'=c_j$ ).

Let us consider what happens when out sequence is mutilated to the extent of $q$ errors, all of which affect the $f_i$ (the $c_j$ being supposed correctly transmitted).

There is no real loss of generality if we assume that the errors affect the first $q$ of the
$f_i$ , the errors being $\epsilon_1$ , $\epsilon_2, \dots, \epsilon_q$ . Since the $c_j$ have been correctly transmitted, the mutilated message can not be in check unless

$c_j = \sum_{i=1}^q k_{ji}(f_i+\epsilon_i) +\sum_{i=q+1}^n k_{ji}f_i =\sum_{i=1}^n k_{ji}f_i + \sum_{i=1}^q k_{ji}\epsilon_i.$

But we recall that, by definition, $c_j =\sum_{i=1}^n k_{ji}f_i$ . Hence the message will fail to check, and the presence of error will be disclosed, unless the $q$ errors $\epsilon_i$ satisfy the system of equations

$\sum_{i=1}^q k_{ji}\epsilon_i = 0$

for $j = 1, 2, \dots, q$ , of which the determinant is

$\Delta = \begin{array}{|cccc|} k_{11} & k_{12} & \dots & k_{1q} \\ k_{21} & k_{22} & \dots & k_{2q} \\ \vdots & & & \vdots \\ k_{q1} & k_{q2} & \dots & k_{qq} \\ \end{array} \, . \ \ \ \ \ \ \ \ (S)$

But our matrix is supposed to be of index $q$ , so that $\Delta \not=0$. It follows, by Lemma 1, that the system (S) has no solution other than $\epsilon_i=0$ , for $i=1,2,\dots, q$ . Hence $q$ errors, confined to the $f_i$ , can not escape disclosure if the reference matrix $Q$ is of index $q$ . By the same argument, applied a fortiori, a set of less than $q$ errors, confined to the $f_i$ , will certainly be disclosed when $Q$ is of index $q$ .

If the reference matrix $Q$ is of index $q$ , we can make the following statement:

Whenever the sequence $f_1, f_2, \dots, f_n, c_1, c_2, \dots, c_q$ is transmitted with errors not affecting the $c_i$ , and not more than $q$ in number, the presence of error will infallibly be disclosed.

We shall hereafter understand that $Q$ is of index $q$ .

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

Posted on 2012/06/05 by wdjoyner

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. The manuscript is being LaTeXed “as we speak”. 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 his this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the third section of his paper. I hope to post more later. (Part 2 is here.)

Section 3: Preliminary characterization of checking procedure

Our problem is to provide convenient and practical accuracy checks upon a sequence of $n$ elements $f_1$ , $f_2$ , $\dots$ , $f_n$ in a finite algebraic field $F$ .

To fix the ideas, let us assume that we are to employ $q$ -element checks $c_1$ , $c_2$ , $\dots$ , $c_q$ upon the sequence $f_1$ , $f_2$ , $\dots$ , $f_n$ . The checks are to be determined by means of a fixed reference matrix

$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)$
of elements of $F$ , the matrix having been suitably constructed according to criteria which will be developed in the following pages. We send, in place of the simple sequence $f_1$ , $f_2$ , $\dots$ , $f_n$ , the amplified sequence

$f_1, f_2, \dots, f_n, c_1, c_2, \dots, c_q$
consisting of the “operand” sequence and the “checking” sequence. The checking sequence contains $q$ elements of $F$ as follows:

$c_j = \sum_{i=1}^n k_{ji}f_i,$

for $j = 1, 2, \dots, q$ . Considerations of telegraphic economy dictate the assumption, made throughout the paper, that $q\leq n$ .

Before laying down specifications for the reference matrix $Q$ , we define a matrix of “index” $q$ as one in which no $q$ -rowed determinant vanishes.

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

Posted on 2012/06/03 by wdjoyner

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. The manuscript is being LaTeXed “as we speak”. 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 his this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the second section of his paper. I hope to post more later. (Part 1 is here.)

Secton 2: Lemmas concerning algebraic fields

Familiarity with primary notions in the theory of finite algebraic fields, and of their algebraic extensions, will naturally be assumed here. Reference is made, however, to Steinitz [St], Dickson [D], Scorza [Sc]. But several points which will be needed very frequently in the following pages are summarized here in a series of lemmas. These lemmas assert properties of any algebraic field, whether it be finite or not.

Lemma 1:
Let $F$ denote an algebraic field. Let the coeefficients $a_{ij}$ in the system of equations

$\begin{array}{c} a_{11}x_1 +a_{12}x_2 +\dots + a_{1n}x_n=0\\ a_{21}x_1 +a_{22}x_2 +\dots + a_{2n}x_n=0\\ \vdots \\ a_{n1}x_1 +a_{n2}x_2 +\dots + a_{nn}x_n=0, \\ \end{array}$

be elements of $F$ . Let $\Delta$ denote the value, in $F$ , of the determinant

$\begin{array}{|ccc|} a_{11} & \dots & a_{1n} \\ \vdots && \\ a_{n1} & \dots & a_{nn} \\ \end{array} \, .$
The system of equations has a solution other than

$x_1 = x_2 = \dots = x_n = 0$

if and only if $\Delta =0$ .

Lemma 2:
Let $F$ denote an algebraic field. Let the coeefficients in the system of equations

$\begin{array}{c} a_{11}x_1 +a_{12}x_2 +\dots + a_{1n}x_n=0\\ a_{21}x_1 +a_{22}x_2 +\dots + a_{2n}x_n=0\\ \vdots \\ a_{k1}x_1 +a_{k2}x_2 +\dots + a_{kn}x_n=0, \\ \end{array}$

be elements of $F$ , and let $k$ be less than $n$ . Then the system of equations certainly has a solution other than
$x_1 = x_2 = \dots = x_n = 0\, .$

Lemma 3:
Let $F$ denote an algebraic field. Let the $a_{ij}$ and the $c_i$ denote elements of $F$ and let at least one of the $c_i$ be different from zero. Consider the determinant

$\Delta = \begin{array}{|ccc|} a_{11} & \dots & a_{1n} \\ \vdots && \\ a_{n1} & \dots & a_{nn} \\ \end{array} \, .$
If $\Delta \not=0$ (Footnote: The case $\Delta = 0$ does not concern us.) then the system of equations

$\begin{array}{c} a_{11}x_1 +a_{12}x_2 +\dots + a_{1n}x_n=0\\ a_{21}x_1 +a_{22}x_2 +\dots + a_{2n}x_n=0\\ \vdots \\ a_{n1}x_1 +a_{n2}x_2 +\dots + a_{nn}x_n=0, \\ \end{array}$

has one and only one solution.

Evidently, when solutions exist for the systems of equations considered in the forgoing three lemmas, such solutions lie entirely in the field $F$ .

The lemma which follows is particularly useful. It is an immediate corollary of Lemma 1.

Lemma 4:
Let $F$ denote an algebraic field. Let the $a_{ij}$ denote elements of $F$ . Then if

$\begin{array}{|ccc|} a_{11} & \dots & a_{1n} \\ \vdots && \\ a_{n1} & \dots & a_{nn} \\ \end{array} =0, \, .$

we can determine at least one sequence of elements $\lambda_1$ , $\lambda_2$ , $\dots$ , $\lambda_n$ , which are not necessarily distinct but certainly are not all equal to zero, such that

$\begin{array}{c} a_{11}\lambda_1 +a_{21}\lambda_2 +\dots + a_{n1}\lambda_n=0\\ a_{12}\lambda_1 +a_{22}\lambda_2 +\dots + a_{n2}\lambda_n=0\\ \vdots \\ a_{1n}\lambda_1 +a_{2n}\lambda_2 +\dots + a_{nn}\lambda_n=0. \\ \end{array}$

Lemma 5:
The algebraic equation of $ $n$ th degree

$a_0x^n + a_1 x^{n-1} + \dots + a_{n-1}x+a_n=0,$

with coefficients in the algebraic field $F$ , can not have more than $n$ roots in $F$ .

Most of the considerations of the present paper will depend, more or less directly, upon these five lemmas.

References:

[D] L. E. Dickson, Linear groups with an exposition of the Galois field theory, B. G. Teubner, Leipzig, 1901. Available here:
http://archive.org/details/lineargroupswith00dickuoft

[Sc] G. Scorza, Corpi numerici e algebre, Giuseppe Principato, 1921.

[St] E. Steinitz, Algebraische theorie der korper, Journal fur die reine und angew. Mathamtik 137(1910)167-308.

Yet Another Mathblog

Monthly Archives: June 2012

Searching with lies, 2

Searching with lies, 1

Lester Hill and error-detecting codes screencast

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

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

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

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

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

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