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 errors

Let the sequence (footnote: Arbitrary error distributions will be considered later. Cf. sections 15-18.)

be transmitted in the form

containing errors which affect the , and errors which affect the .

Let . Then, to avoid discussing again the case already considered, we assume that at least one of the two integers

is greater than .

Let the errors among the be , affecting the . Without loss in generality, we may assume that the errors affecting the are , so that the first of the are transmitted in error.

Suppose that the mutilated sequence is in full check. Then:

or

whence

where and where in and may, of course, be

equal to .

It follows that

where and where denotes a polynomial in the errors .

The index of the reference matrix being , the determinant

of the systems of equations

is not zero. Hence if all the $b_j$ are equal to zero, Lemma 1 demands that all the , for , be equal to zero, contrary to hypothesis.

If at least one of the is different from , Lemma 3 shows that are uniquely determined as functions of the , and therefore as functions of :

the functions being, of course, rational functions. But, by assumption, all of the $\delta_j$, except , vanish. Hence () is a rational function of .

We conclude that if the mutilated message, containing errors, is to check up, so that the presence of error can escape detection, of the errors must be carefully adjusted as rational functions of the remaining errors.

It is easy to measure the chance that mere accidents of erroneous telegraphic transmittal might effect this adjustment. Let denote the total number of elements in the finite algebraic field which we are dealing. When an error is made in transmitting a sequence of elements of , the error may evidently have any one of values — an error with the value being no real error at all. It is therefore clear that our set of errors will enjoy only chance in of being accidentally adjusted so as to escape detection.

When errors occur among the and errors occur among the in the transmittal of the sequence , the errors being all of accidental telegraphic origin, the presence of error will infallibly be disclosed if ; and will enjoy a -in- of escaping disclosure if either of the two integers , is greater than .

This statement summarizes the results of the present section and those of section 4.

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