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.

One thought on “Lester Hill’s “The checking of the accuracy …”, part 7

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

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s