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

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

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

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.

# 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$.