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

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

or

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

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

  1. Pingback: Lester Hill’s “The checking of the accuracy …”, part 6 « 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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s