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

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

Here is just the 15th section of his paper. I hope to post more later. (Part 14 is here.)

Lemma concerning reference matrices

The general reference matrix of Section 3 was:

$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)$
the $k_{ij}$ being elements of any given finite algebraic field $F$, and $q$ being less than or equal to $n$.

This matrix contains determinants of order $r$ with $r=1,2,\dots, q$ — determinants of first order ($r=1$) being single elements of the matrix.

We recall that if $f_1$, $f_2, \dots, f_{s}$ is an $s$ element operand
sequence in $F$, a $t$-element check based upon the matrix $Q$ is:

$c_j = \sum_{i=1}^{s} k_{ji} f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, t).$
it being understood that $s\leq n$, $t\leq q$.

Let $Q$ contain no vanishing determinant of any order: Let $c_1$, $c_2, \dots, c_{t}$ be a $t$-element check, $t\leq q$, on the operand sequence $f_1$, $f_2$, \dots, $f_{s}$, $s\leq n$. Let $v$ be a positive integer less than or equal to $s+t$. If, in the transmittal of the sequence

$f_1, f_2, \dots, f_{s}, c_1, c_2, \dots, c_{t},$
errors occur in $v$ of its $s+t$ elements, whatever the distribution of the errors, the presence of error will certainly be disclosed, or will enjoy only a $1$-in-$(\Gamma-1)^t$ chance of escaping disclosure, according as $v$ is, or is not, less than $t+1$. In this statement, $\Gamma$ denotes the total number of elements in the field $F$.

proof:
Case 1:
Let all $v$ errors fall among the $c_1, c_2, \dots, c_{t}$. The presence of error is evidently certain to be disclosed.

Case 2:
Let all $v$ errors fall among the $f_1, f_2, \dots, f_{s}$.

(2.1): Let $v\leq t$. There is no loss of generality of we assume [This assumption implies $v\leq s$. – wdj] the $v$ errors are $\epsilon_1$, $\epsilon_2, \dots, \epsilon_v$, affecting $f_1, f_2, \dots, f_{v}$. The errors cannot escape disclosure. For, to do so, they would have to satisfy the system of homogeneous linear equations:

$\sum_{i=1}^{v} k_{ji} \epsilon_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, t).$
in which the matrix of coefficients $k_{ji}$ contains no vanishing determinant of any order, and which, therefore admits no solution other than $\epsilon_i=0$ ($i = 1, 2, \dots, v$).

For this treatment of the errors, compare Sections 4, 5.

Case 3:
Let $z$ errors fall among the $f_i$ and $w=v-z$ errors fall among the $c_j$. Without loss in generality, we may assume that the errors are $\epsilon_1$, $\epsilon_2, \dots, \epsilon_z$, affecting $f_1, f_2, \dots, f_{z}$, and $\delta_{j_1}$, $\delta_{j_2}, \dots, \delta_{j_w}$, affecting $c_{j_1}$, $c_{j_2}, \dots, c_{j_w}$.

(3.1): Let $z+w\leq t$. Writing $t=v+h=z+w+h$, where $h$ denotes a non-negative integer which may or may not be zero, we have $t-w = z+h$. Hence $z+h$ of the $c_j$ are transmitted without error.

If the presence of error is to escape disclosure, we see, therefore, that the $z$ errors $\epsilon_i$ must satisfy the system of at least $z$ homogeneous linear equations:

$\sum_{i=1}^{z} k_{r_m,i} \epsilon_i,\ \ \ \ \ \ \ (m = 1, 2, \dots, z+h),$
where the indices $r_m$ denote a set of $z+h$ integers selected from $1, 2, \dots, t$. But the matrix of coefficients in this system contains no vanishing determinant, so that the only solution would be $\epsilon_i=0$ ($i = 1, 2, \dots, z$).

For details in this treatment of errors, see Section \ref{sec:5}.

(3.2): Let $z+w> t$. Then $w = t-(z-h)$, where $h$ denotes a positive integer. Assuming that the presence of error is to escape detection, we see, therefore, that the $v$ errors must satisfy $t$ linear equations as follows:

($\alpha$) a system of $z-h$ equations involving only the errors $\epsilon_i$, ($i = 1, 2, \dots, z$), and homogeneous in these $z$ errors;

($\beta$) a system of $w$ equations involving all $v$ errors.

Since the matrix of the coefficients in the system ($\alpha$) contains no vanishing determinant, we can solve this system for $z-h$ of the $\epsilon_i$ as rational functions of the remaining $h$ of the $\epsilon_i$.

The system ($\beta$) determines all errors affecting the $c_j$ — that is, all the errors $\delta_{j_i}$ — as polynomial functions of the $\epsilon_i$, ($i = 1, 2, \dots, z$).

Hence, all told, $(z-h)+w$ errors are determined as rational functions of the remaining $h$ errors. In other words, $v-t$ errors determine the other $t$ errors.

An accidental error can assume any one of $\Gamma -1$ values, there being $\Gamma$ elements in the finite field $F$. Hence the chance that the errors will check up, and thus escape disclosure, is only $1$-in-$(\Gamma-1)^t$.
QED

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

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

Here is just the 14th section of his paper. I hope to post more later. (Part 13 is here.)

Illustration of checking in the field $F_{101}$

We wish to provide checks upon arbitrary sequences $f_1$, $f_2$, …, $f_n$ of elements of any given finite algebraic field. Operations in the field $F_{101}$ can be used to illustrate all the essential points arising in this connection.

Example 1: Check of Type A upon a sequence $f_1$, $f_2$, …, $f_{10}$. Suppose that we wish, in a certain message, to transmit the numerical sequence

$38460000600800000299.$
The origin and significance of this sequence in the following form, in which it appears as a sequence of ten elements of $F_{101}$:

$\begin{array}{cccccccccc} 38 & 46 & 00 & 00 & 60 & 08 & 00 & 00 & 02 & 99\\ f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 & f_9 & f_{10}\\ \end{array}$
A five-element check ($q=5$) is obtained by the simple tabulation which follows. We use Table 4, noting that in each of the nine rows, the one-hundred columns are shown in four sections, there being twenty-five columns in each section.

For the first element, 38, in the operand sequence $f_i$, place ruler under the proper section of row 1 of the Table. In row 1, read: 13 in column 38, 39 in column 13, 16 in column 39, 48 in column 16, 43 in column 48. Start a tabulation:

$13\quad 39\quad 16 \quad 48 \quad 43.$
For the second element, 46, in the operand sequence, place ruler under the proper section of row 2 of the Table. In row 2, read: 83 in column 46, 29 in column 83, 15 in column 29, 60 in column 15, 38 in column 60. Continue the tabulation:

$13\quad 39\quad 16 \quad 48 \quad 43\\ 83\quad 29\quad 15 \quad 60 \quad 38$
Since the third and fourth elements of the operand sequence are equal to zero, skip them entirely. For the fifth element, 60, read in row 5 of the Table: 76 in column 60, 2 in column 76, 16 in column 2, 27 in column 16, 14 in column 27. Continue the tabulation:

$13\quad 39\quad 16 \quad 48 \quad 43\\ 83\quad 29\quad 15 \quad 60 \quad 38\\ 76\quad 2\quad 16 \quad 27 \quad 14$

Proceed in this manner to the ninth element, 2, inclusive of the operand sequence. There being no tenth row in the Table, simply add the tenth element, 99, of the operand sequence in each vertical column of the tabulation. The full tabulation is:

$\begin{array}{rrrrrl} 13 & 39 & 16 & 48 & 43 & \\ 83 & 29 & 15 & 60 & 38 & \\ 76 & 2 & 16 & 27 & 14 & \\ 99 & 51 & 63 & 60 & 86 & \\ 84 & 94 & 9 & 75 & 19 & \\ \hline 454 & 314 & 218 & 369 & 299 & sum\ in\ ZZ\\ 50 & 11 & 16 & 66 & 97 & sum\ in\ F_{101}\\ \end{array}$
The five-element check is therefore:

$c_1 = 50, c_2 = 11, c_3 = 16, c_4 = 66, c_5 = 97.$
We transmit telegraphically the sequence of fifteen elements of $F_{101}$:

$38 \quad 46\quad 00\quad 00 \quad 60\quad 08 \quad 00 \quad 00\quad 02\quad 99\quad 50 \quad 11\quad 16 \quad 66 \quad 97.$
A discussion of possible errors will be given in another section. we simply note here that the $c_j$’s, as determined in the above tabulation, are:

$c_1 = \sum_{i=1}^{10} a_i f_i,\quad c_2 = \sum_{i=1}^{10} a_i^2 f_i,\quad \dots, c_5 = \sum_{i=1}^{10} a_i^5 f_i.$
If only a one-element check had been desired, we should have taken $c_1=50$, and a one-column tabulation would have sufficed. If a two-element check had been desired, we should have taken $c_1=50$, $c_2=11$ and a two-column tabulation would have sufficed. Etc.

If the operand sequence $f_i$ contains less than $10$ elements, the procedure, to determine check of Type A, is obvious. A $q$-element check upon $f_1$, $f_2$, \dots, $f_{n}$, with $n<10$, is as stated:

$c_j = \sum_{i=1}^{10} a_i^j f_i,\ \ \ \ \ \ \ j = 1, 2, \dots, q,$
with $q=1,2,3,4,5$. The manner of its evaluation, by means of Table 4, is clear.

Example 2: Check of Type B upon a sequence $f_1$, $f_2$, … , $f_{8}$.

Suppose that we desire a five-element check upon the numerical sequence $6500000000001794$ – that is, upon

$\begin{array}{cccccccc} 65 & 00 & 00 & 00 & 00 & 00 & 17 & 94\\ f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 \\ \end{array}$
We wish to evaluate $c_j = \sum_{i=1}^{8} b_i^j f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, 5)$. The tabulation is as follows:

$\begin{array}{rrrrrl} 94 & 80 & 38 & 13 & 39 & row\ 1,\ Table\ 4,\ read:\ 94\ in\ column\ 65,\ etc. \\ 90 & 19 & 59 & 45 & 60 &row\ 7,\ read:\ 90\ in\ column\ 17,\ etc. \\ 94 & 94 & 94 & 94 & 94 & \\ \hline 278 & 193 & 191 & 152 & 193 & sum\ in\ ZZ\\ 76 & 92 & 90 & 51 & 92 & sum\ in\ F_{101}\\ c_1 & c_2 & c_3 & c_4 & c_5 & \\ \end{array}$

Example 3: Check of Type A upon the same operand sequence as in Example 2.

We wish to evaluate $c_j = \sum_{i=1}^{8} a_i^j f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, 5)$. The tabulation is as follows:

$\begin{array}{rrrrrl} 94 & 80 & 38 & 13 & 39 & \\ 90 & 19 & 59 & 45 & 60 & \\ 97 & 41 & 9 & 34 & 5 &row\ 8,\ Table\ 4,\ read:\ 97\ in\ col.\ 94,\ etc. \\ \hline 281 & 140 & 106 & 92 & 104 & sum\ in\ ZZ\\ 79 & 39 & 5 & 92 & 3 & sum\ in\ F_{101}\\ c_1 & c_2 & c_3 & c_4 & c_5 & \\ \end{array}$

Example 4: Check of Type A and B upon the operand sequence

$\begin{array}{ccccccc} 00 & 65 & 00 & 00 & 00 & 17 & 94\\ f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 \\ \end{array}$
We wish to evaluate

$c_j = \sum_{i=1}^{7} a_i^j f_i= \sum_{i=1}^{7} b_i^j f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, 5).$
The tabulation is as follows:

$\begin{array}{rrrrrl} 58 & 30 & 19 & 76 & 1 & row\ 2,\ Table\ 4,\ read:\ 58\ in\ col.\ 65,\ etc. \\ 21 & 20 & 96 & 77 & 6 &row\ 6,\ read:\ 21\ in\ col.\ 17,\ etc. \\ 58 & 10 & 47 & 29 & 5 &row\ 7,\ read:\ 58\ in\ col.\ 94,\ etc. \\ \hline 137 & 60 & 162 & 182 & 12 & sum\ in\ ZZ\\ 36 & 60 & 61 & 81 & 12 & sum\ in\ F_{101}\\ c_1 & c_2 & c_3 & c_4 & c_5 & \\ \end{array}$

Questions of rigor will be discussed in a subsequent section. It may be noted here, however, that our checks make very
nice discriminations. Thus, although the operand sequence in Examples 3 and 4 are closely similar, the checking sequences are widely different.

It will now be apparent to those who are acquainted with the problems of code communication that we are in a position to furnish powerful and economical checks on message sequences in any conceivable telegraphic system. We have only to partition messages into groups of not more than ten, or not more that eight, elements each — according to any
definite prearrangement — and to check each group with a $q$-check, $q=1,2,3,4,5$ (as may be arranged), of Type A or of Type B. If it is desired to work with longer groups, we have only to enlarge Table 4. The limitations introduced in this paper may be largely overcome, or removed, by suitable amplification of the Table employed.