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