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

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.

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

  1. Pingback: Lester Hill’s “The checking of the accuracy …”, part 5 « Yet Another Mathblog

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s