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

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

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 third section of his paper. I hope to post more later. (Part 2 is here.)

Section 3: Preliminary characterization of checking procedure

Our problem is to provide convenient and practical accuracy checks upon a sequence of $n$ elements $f_1$, $f_2$, $\dots$, $f_n$ in a finite algebraic field $F$.

To fix the ideas, let us assume that we are to employ $q$-element checks $c_1$, $c_2$, $\dots$, $c_q$ upon the sequence $f_1$, $f_2$, $\dots$, $f_n$. The checks are to be determined by means of a fixed reference matrix

$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)$
of elements of $F$, the matrix having been suitably constructed according to criteria which will be developed in the following pages. We send, in place of the simple sequence $f_1$, $f_2$, $\dots$, $f_n$, the amplified sequence

$f_1, f_2, \dots, f_n, c_1, c_2, \dots, c_q$
consisting of the “operand” sequence and the “checking” sequence. The checking sequence contains $q$ elements of $F$ as follows:

$c_j = \sum_{i=1}^n k_{ji}f_i,$

for $j = 1, 2, \dots, q$. Considerations of telegraphic economy dictate the assumption, made throughout the paper, that $q\leq n$.

Before laying down specifications for the reference matrix $Q$, we define a matrix of “index” $q$ as one in which no $q$-rowed determinant vanishes.

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

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 second section of his paper. I hope to post more later. (Part 1 is here.)

Secton 2: Lemmas concerning algebraic fields

Familiarity with primary notions in the theory of finite algebraic fields, and of their algebraic extensions, will naturally be assumed here. Reference is made, however, to Steinitz [St], Dickson [D], Scorza [Sc]. But several points which will be needed very frequently in the following pages are summarized here in a series of lemmas. These lemmas assert properties of any algebraic field, whether it be finite or not.

Lemma 1:
Let $F$ denote an algebraic field. Let the coeefficients $a_{ij}$ in the system of equations

$\begin{array}{c} a_{11}x_1 +a_{12}x_2 +\dots + a_{1n}x_n=0\\ a_{21}x_1 +a_{22}x_2 +\dots + a_{2n}x_n=0\\ \vdots \\ a_{n1}x_1 +a_{n2}x_2 +\dots + a_{nn}x_n=0, \\ \end{array}$

be elements of $F$. Let $\Delta$ denote the value, in $F$, of the determinant

$\begin{array}{|ccc|} a_{11} & \dots & a_{1n} \\ \vdots && \\ a_{n1} & \dots & a_{nn} \\ \end{array} \, .$
The system of equations has a solution other than

$x_1 = x_2 = \dots = x_n = 0$

if and only if $\Delta =0$.

Lemma 2:
Let $F$ denote an algebraic field. Let the coeefficients in the system of equations

$\begin{array}{c} a_{11}x_1 +a_{12}x_2 +\dots + a_{1n}x_n=0\\ a_{21}x_1 +a_{22}x_2 +\dots + a_{2n}x_n=0\\ \vdots \\ a_{k1}x_1 +a_{k2}x_2 +\dots + a_{kn}x_n=0, \\ \end{array}$

be elements of $F$, and let $k$ be less than $n$. Then the system of equations certainly has a solution other than
$x_1 = x_2 = \dots = x_n = 0\, .$

Lemma 3:
Let $F$ denote an algebraic field. Let the $a_{ij}$ and the $c_i$ denote elements of $F$ and let at least one of the $c_i$ be different from zero. Consider the determinant

$\Delta = \begin{array}{|ccc|} a_{11} & \dots & a_{1n} \\ \vdots && \\ a_{n1} & \dots & a_{nn} \\ \end{array} \, .$
If $\Delta \not=0$ (Footnote: The case $\Delta = 0$ does not concern us.) then the system of equations

$\begin{array}{c} a_{11}x_1 +a_{12}x_2 +\dots + a_{1n}x_n=0\\ a_{21}x_1 +a_{22}x_2 +\dots + a_{2n}x_n=0\\ \vdots \\ a_{n1}x_1 +a_{n2}x_2 +\dots + a_{nn}x_n=0, \\ \end{array}$

has one and only one solution.

Evidently, when solutions exist for the systems of equations considered in the forgoing three lemmas, such solutions lie entirely in the field $F$.

The lemma which follows is particularly useful. It is an immediate corollary of Lemma 1.

Lemma 4:
Let $F$ denote an algebraic field. Let the $a_{ij}$ denote elements of $F$. Then if

$\begin{array}{|ccc|} a_{11} & \dots & a_{1n} \\ \vdots && \\ a_{n1} & \dots & a_{nn} \\ \end{array} =0, \, .$

we can determine at least one sequence of elements $\lambda_1$, $\lambda_2$, $\dots$, $\lambda_n$, which are not necessarily distinct but certainly are not all equal to zero, such that

$\begin{array}{c} a_{11}\lambda_1 +a_{21}\lambda_2 +\dots + a_{n1}\lambda_n=0\\ a_{12}\lambda_1 +a_{22}\lambda_2 +\dots + a_{n2}\lambda_n=0\\ \vdots \\ a_{1n}\lambda_1 +a_{2n}\lambda_2 +\dots + a_{nn}\lambda_n=0. \\ \end{array}$

Lemma 5:
The algebraic equation of \$$n$th degree

$a_0x^n + a_1 x^{n-1} + \dots + a_{n-1}x+a_n=0,$

with coefficients in the algebraic field $F$, can not have more than $n$ roots in $F$.

Most of the considerations of the present paper will depend, more or less directly, upon these five lemmas.

References:

[D] L. E. Dickson, Linear groups with an exposition of the Galois field theory, B. G. Teubner, Leipzig, 1901. Available here:
http://archive.org/details/lineargroupswith00dickuoft

[Sc] G. Scorza, Corpi numerici e algebre, Giuseppe Principato, 1921.

[St] E. Steinitz, Algebraische theorie der korper, Journal fur die reine und angew. Mathamtik 137(1910)167-308.

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

Backstory: Lester Saunders Hill wrote an unpublished notes, 40 pages, undated but probably written in mid- to late 1920s, titled “The checking of the accuracy of transmittal of telegraphic communications by means of operations in finite algebraic fields”. In the 1960s this was given to David Kahn by Hill’s widow. These notes were typewritten, but mathematical symbols, tables, insertions, and some footnotes were often handwritten. These notes are 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 introductory first section of his paper. I hope to post more later.

Section 1: The problem considered

The forms of code in current use for the economical transmittal of cable and radio messages employ, almost uniformly, the so-called ”pronounceable” combinations. Pronounceability is estimated in terms of letter groups which commonly occur in one or more of eight designated ”telegraphic” languages: English, French, Spanish, etc. International regulations have, in fact, prescribed a system, of charges according to which a secret five-letter word is regarded, in the word count, as one-half of a telegraphic word, or as a full telegraphic word, according to as it is, or is not, pronounceable.

There is now descernible a definite tendancy to abandon this quite arbitrary pronounceability rule, which has heretofore hampered the development of code and cipher communication. And it seems not unlikely that, at some early session of the Interbational Telegraph Congress, all secret five-letter combinations will be placed upon the same basis with respect to transmittal charges.

A mathematical problem of considerable scientific and practical interest arises in this connection. Messages written in pronounceable code or cipher contain within themselves certain checks upon the accuracy of their telegraphic transmittal. But sequences of unpronounceable groups will generally be quite arbitrary, and no such internal check will ordinarily be available. The outstanding requirement is some device capable of protecting totally unrestricted sequences, in a telegraphically economical way, against the hazards of faulty transmittal.

Let the finite set $C$ of signs (letters, numerals, etc) upon which a given system of communication is based – plain-language, code, or cipher system – be placed in correspondence with the elements of a finite algebraic field $F$. Then the problem of checking sequences of signs in $C$ becomes that of checking sequences of elements in $F$. As well-known, if we denote by $\Gamma$ the number of elements, including the zero and unit elements, of a finite field $F$, then $\Gamma$ is one of the numbers:

$2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, \dots ,$

that is to say, $\Gamma$ is of the form $\Gamma = p^r$, where $p$ denotes a prime positive integer greater than $1$ and $r$ denotes a positive integer. Conversely, if $\Gamma$ is an integer of this form, we can very easily set up finite algebraic fields with $\Gamma$ elements. In devising a scheme of checks for messages based upon the system $C$ of communications with $n$ distinct signs, we should normally work with a field $F$ the number, $\Gamma$, of whose elements differs as little as possible form $n$. But this is not essential.

Our problem, viewed form the standpoint of mathematics, is simply that of providing economical and rigorous checks, easily applied in a practical way, upon the accuracy of transmittal of arbitrary sequences of elements in a finite algebraic field.

The method suggested will be applicable to telegraphic messages of any type: plain-language, code, cipher, cipher-code. It will, however, undoubtedly, be found susceptible of fundamental improvement in many respects; and it will probably yield to other, and more definitely practical, procedures that may subsequently be constructed be upon a basis of number-theoretical operations. The present paper will have served its purpose if it succeeds in directing attention to certain hitherto neglected practical possibilites inherent in elementary algebraic manipulations.