Category Archives: math

Lester Hill and error-detecting codes screencast

Posted on by

Lester Saunders Hill (1890-1961) is famous for having discovered the Hill cryptosystem (en.wikipedia.org/wiki/Hill_cipher). It was recently discovered that Hill wrote an unpublished paper (undated but probably written in the 1920s) in which he discovered a class of error-correcting codes not found by others until decades later. This screencast is a non-technical exposition into the history of this side of Hill’s work.

Thanks to Chris Christensen, David Kahn, and Rene Stein (librarian for NSA Cryptologic Museum) for material on which this presentation is based. For more on the “message protector”, see http://www.nku.edu/~christensen/Cryptological%20History%20Symposium.pdf.

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

Posted on by

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.

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

Posted on by

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


Section 6: Arbitrary distrbution of errors affecting the f_i and the c_j

It is highly desirable, although not strictly necessary, to fashion the reference matrix Q in such a manner that every determinant contained in it, of every order, be different from zero.

Reference matrices of a practical type, and without a vanishing determinant of any order, may be construted in certain finite fields F by very direct methods which can be more easily illustrated than described. It will be expedient at this poin, even at the expense of breaking the continuity of our discussion, to introduce concrete examples of operations in finite fields, and to show how reference matrices be conveniently set up in particular cases. The desirability of contriving that such matrices contain no vanishing determinant can then be brought out more effectively. The examination of arbitrary distributions of errors among the n+q elements of a telegraphic sequence

f_1, f_2, \dots, f_n, c_1, c_2, \dots, c_q

can be deferred, therefore, until later.

But, before going into details, we will describe the general form of reference matrix to be employed in all cases.

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

Posted on by

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 q errors \epsilon_i

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

f_1, f_2, \dots, f_n,\ c_1, c_2, \dots, c_q
be transmitted in the form

f_1', f_2', \dots, f_n',\ c_1', c_2', \dots, c_q' \, ,
containing t\geq q errors which affect the f_i, and h\geq 0 errors which affect the c_j.

Let t=q+s. Then, to avoid discussing again the case already considered, we assume that at least one of the two integers s, h
is greater than 0.

Let the errors among the c_j be \delta_{j_1}, \delta_{j_2}, \dots , \delta_{j_h}, affecting the c_{j_1}, c_{j_2}, \dots , c_{j_h}. Without loss in generality, we may assume that the t errors affecting the f_i are \epsilon_1, \epsilon_2, \dots, \epsilon_t, so that the first t of the f_i are transmitted in error.

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

\sum_{i=1}^t k_{ji}(f_i+\epsilon_i)+\sum_{i=t+1}^n k_{ji}f_i =c_j+\delta_j

or

\sum_{i=1}^n k_{ji}f_i+\sum_{i=1}^t k_{ji}\epsilon_i =c_j+\delta_j

whence

\sum_{i=1}^t k_{ji}\epsilon_i=\delta_j

where j=1,2,\dots, q and where \delta_j in c_j and may, of course, be
equal to 0.

It follows that

\sum_{i=1}^q k_{ji}\epsilon_i = \delta_j - \sum_{i=1}^t k_{ji}\epsilon_i = b_j = \phi_j(\epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_j),
where j=1,2,\dots, q and where \phi_j denotes a polynomial in the errors \epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_j.

The index of the reference matrix being q, the determinant

\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 the systems of equations

\sum_{i=1}^q k_{ji}\epsilon_i = b_j \ \ \ \ \ \ \ \ \ \ (j=1,2,\dots, q)

is not zero. Hence if all the $b_j$ are equal to zero, Lemma 1 demands that all the \epsilon_i, for i=1, 2, \dots, q, be equal to zero, contrary to hypothesis.

If at least one of the b_j is different from 0, Lemma 3 shows that \epsilon_{1}, \epsilon_{2}, \dots , \epsilon_q are uniquely determined as functions of the b_j, and therefore as functions of \epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_1, \delta_2, \dots, \delta_q:

\epsilon_i = \xi_i (\epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_1, \delta_2, \dots, \delta_q),\ \ \ \ \ \ \ \ \ \ (j=1,2,\dots, q)

the functions \xi_i being, of course, rational functions. But, by assumption, all of the $\delta_j$, except \delta_{j_1}, \dots, \delta_{j_h}, vanish. Hence \epsilon_i (i=1,2,\dots, q) is a rational function of \epsilon_{q+1}, \epsilon_{q+2}, \dots , \epsilon_t, \delta_{j_1}, \delta_{j_2}, \dots, \delta_{j_h}.

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

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


When t=q+s errors occur among the f_i and h errors occur among the c_j in the transmittal of the sequence f_1, f_2, \dots, f_n,\ c_1, c_2, \dots, c_q, the errors being all of accidental telegraphic origin, the presence of error will infallibly be disclosed if h=s=0; and will enjoy a 1-in-(\Gamma -1)^q of escaping disclosure if either of the two integers h, s is greater than 0.

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

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

Posted on by

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

Posted on by

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

Posted on by

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

Posted on by

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.

SymPy and the GSoC

Posted on by

Google has announced the results for Google Summer of Code. The following projects have been accepted for SymPy:

(Project, Student, Mentor, Link to proposal on the wiki)
– Category Theory Module, Sergiu Ivanov, Tom Bachmann
– Density Operators for Quantum Module in sympy.physics.quantum, Guru
Devanla, Brian Granger (co-mentor Sean Vig)
– Enhancements to sympy.physics.mechanics, Angadh Nanjangud, Gilbert Gede
– Group Theory, Aleksandar Makelov, David Joyner (Aaron Meurer co-mentor)
– Implicit Plotting Module, Bharath M R, Aaron Meurer
– Vector Analysis, Stefan Krastanov, Matthew Rocklin

I will help mentor Aleksandar Makelov’s work on group theory. He is a freshman at Harvard.

A remark on mathematical research

Posted on by

Ira Glass, of This American Life (http://www.thisamericanlife.org/), did an excellent four-part interview where he talked at length about writing news stories. They are here:

Ira Glass on Storytelling:
part 1 of 4 http://www.youtube.com/watch?v=loxJ3FtCJJA&feature=relmfu
part 2 of 4 http://www.youtube.com/watch?v=KW6x7lOIsPE&feature=fvwrel
part 3 of 4 http://www.youtube.com/watch?v=BI23U7U2aUY&feature=fvwrel
part 4 of 4 http://www.youtube.com/watch?v=baCJFAGEuJM&feature=relmfu

I thought a lot of what he said was based on general principles which applied to mathematical research as well. Here is perhaps what he would have said if he was talking about mathematics, sometimes with direct quotes from his interview:

There are two building blocks to a idea for a paper

  1. The problem or question. This is sometimes an issue in the intersection of two fields or a question of why some object of interest behaves the way you think it does, based on an example you know.
  2. The revelation. This might be a key example or technique that will hopefully reveal the answer to your question.

You can have a great question, but if they don’t turn out to have any useful techniques or examples to work with, your idea is uninteresting. Conversely you can have a significant revelation with a fantastically powerful method, but if the problem or examples themselves are uninteresting, again you’ve got a weak idea.

You have to set aside just as much time looking for good ideas as you do producing them. In other words, the work of thinking up a good idea to write about is as much work and time as writing it up.

Not enough gets said about the importance of abandoning crap. Most of your story ideas are going to be crap. That’s okay because the only way you can surface great ideas is by going through a lot of crappy ones. The only reason you want to be doing this is to make something memorable and special.

“The thing I’d like to say to you with all my heart is that most everybody I know who does interesting creative work went through a phase of years where with their good taste, they could tell what they were doing wasn’t as good as they wanted it to be … it didn’t have that special thing they wanted it to have … Everybody goes through that phase … and the most important thing you can do is do a lot of work.”