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$

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

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

M	T	W	T	F	S	S
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30

Yet Another Mathblog

Share this:

Like this:

Related

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

Leave a Reply Cancel reply