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

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 like this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the 15th section of his paper. I hope to post more later. (Part 14 is here.)


 

Lemma concerning reference matrices

The general reference matrix of Section 3 was:

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)
the k_{ij} being elements of any given finite algebraic field F, and q being less than or equal to n.

This matrix contains determinants of order r with r=1,2,\dots, q — determinants of first order (r=1) being single elements of the matrix.

We recall that if f_1, f_2, \dots, f_{s} is an s element operand
sequence in F, a t-element check based upon the matrix Q is:

c_j = \sum_{i=1}^{s} k_{ji} f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, t).
it being understood that s\leq n, t\leq q.

Let Q contain no vanishing determinant of any order: Let c_1, c_2, \dots, c_{t} be a t-element check, t\leq q, on the operand sequence f_1, f_2, \dots, $f_{s}$, $s\leq n$. Let v be a positive integer less than or equal to s+t. If, in the transmittal of the sequence

f_1, f_2, \dots, f_{s}, c_1, c_2, \dots, c_{t},
errors occur in v of its s+t elements, whatever the distribution of the errors, the presence of error will certainly be disclosed, or will enjoy only a 1-in-(\Gamma-1)^t chance of escaping disclosure, according as $v$ is, or is not, less than t+1. In this statement, \Gamma denotes the total number of elements in the field F.

proof:
Case 1:
Let all v errors fall among the c_1, c_2, \dots, c_{t}. The presence of error is evidently certain to be disclosed.

Case 2:
Let all v errors fall among the $f_1, f_2, \dots, f_{s}$.

(2.1): Let v\leq t. There is no loss of generality of we assume [This assumption implies v\leq s. – wdj] the $v$ errors are \epsilon_1, \epsilon_2, \dots, \epsilon_v, affecting f_1, f_2, \dots, f_{v}. The errors cannot escape disclosure. For, to do so, they would have to satisfy the system of homogeneous linear equations:

\sum_{i=1}^{v} k_{ji} \epsilon_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, t).
in which the matrix of coefficients k_{ji} contains no vanishing determinant of any order, and which, therefore admits no solution other than \epsilon_i=0 (i = 1, 2, \dots, v).

For this treatment of the errors, compare Sections 4, 5.

Case 3:
Let z errors fall among the f_i and w=v-z errors fall among the c_j. Without loss in generality, we may assume that the errors are \epsilon_1, \epsilon_2, \dots, \epsilon_z, affecting f_1, f_2, \dots, f_{z}, and \delta_{j_1}, \delta_{j_2}, \dots, \delta_{j_w}, affecting c_{j_1}, c_{j_2}, \dots, c_{j_w}.

(3.1): Let z+w\leq t. Writing t=v+h=z+w+h, where h denotes a non-negative integer which may or may not be zero, we have t-w = z+h. Hence z+h of the c_j are transmitted without error.

If the presence of error is to escape disclosure, we see, therefore, that the z errors $\epsilon_i$ must satisfy the system of at least z homogeneous linear equations:

\sum_{i=1}^{z} k_{r_m,i} \epsilon_i,\ \ \ \ \ \ \ (m = 1, 2, \dots, z+h),
where the indices r_m denote a set of z+h integers selected from 1, 2, \dots, t. But the matrix of coefficients in this system contains no vanishing determinant, so that the only solution would be \epsilon_i=0 (i = 1, 2, \dots, z).

For details in this treatment of errors, see Section \ref{sec:5}.

(3.2): Let z+w> t. Then w = t-(z-h), where $h$ denotes a positive integer. Assuming that the presence of error is to escape detection, we see, therefore, that the v errors must satisfy t linear equations as follows:

(\alpha) a system of z-h equations involving only the errors \epsilon_i, (i = 1, 2, \dots, z), and homogeneous in these $z$ errors;

(\beta) a system of w equations involving all v errors.

Since the matrix of the coefficients in the system (\alpha) contains no vanishing determinant, we can solve this system for $z-h$ of the $\epsilon_i$ as rational functions of the remaining h of the \epsilon_i.

The system (\beta) determines all errors affecting the c_j — that is, all the errors \delta_{j_i} — as polynomial functions of the \epsilon_i, (i = 1, 2, \dots, z).

Hence, all told, (z-h)+w errors are determined as rational functions of the remaining h errors. In other words, v-t errors determine the other $t$ errors.

An accidental error can assume any one of $\Gamma -1$ values, there being \Gamma elements in the finite field F. Hence the chance that the errors will check up, and thus escape disclosure, is only 1-in-(\Gamma-1)^t.
QED

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

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 like this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the 14th section of his paper. I hope to post more later. (Part 13 is here.)

 


 

Illustration of checking in the field F_{101}

 

We wish to provide checks upon arbitrary sequences f_1, f_2, …, f_n of elements of any given finite algebraic field. Operations in the field F_{101} can be used to illustrate all the essential points arising in this connection.

Example 1: Check of Type A upon a sequence f_1, f_2, …, f_{10}. Suppose that we wish, in a certain message, to transmit the numerical sequence

38460000600800000299.
The origin and significance of this sequence in the following form, in which it appears as a sequence of ten elements of F_{101}:

\begin{array}{cccccccccc}  38  & 46  & 00  & 00 & 60  & 08  & 00 & 00  & 02  & 99\\  f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 & f_9 & f_{10}\\  \end{array}
A five-element check (q=5) is obtained by the simple tabulation which follows. We use Table 4, noting that in each of the nine rows, the one-hundred columns are shown in four sections, there being twenty-five columns in each section.

For the first element, 38, in the operand sequence f_i, place ruler under the proper section of row 1 of the Table. In row 1, read: 13 in column 38, 39 in column 13, 16 in column 39, 48 in column 16, 43 in column 48. Start a tabulation:

13\quad 39\quad 16 \quad 48 \quad 43.
For the second element, 46, in the operand sequence, place ruler under the proper section of row 2 of the Table. In row 2, read: 83 in column 46, 29 in column 83, 15 in column 29, 60 in column 15, 38 in column 60. Continue the tabulation:

13\quad 39\quad 16 \quad 48 \quad 43\\  83\quad 29\quad 15 \quad 60 \quad 38
Since the third and fourth elements of the operand sequence are equal to zero, skip them entirely. For the fifth element, 60, read in row 5 of the Table: 76 in column 60, 2 in column 76, 16 in column 2, 27 in column 16, 14 in column 27. Continue the tabulation:

13\quad 39\quad 16 \quad 48 \quad 43\\  83\quad 29\quad 15 \quad 60 \quad 38\\  76\quad 2\quad 16 \quad 27 \quad 14

Proceed in this manner to the ninth element, 2, inclusive of the operand sequence. There being no tenth row in the Table, simply add the tenth element, 99, of the operand sequence in each vertical column of the tabulation. The full tabulation is:

\begin{array}{rrrrrl}  13 & 39 & 16  & 48  & 43  & \\  83 & 29 & 15  & 60  & 38  & \\  76 & 2 & 16  & 27  & 14  & \\  99 & 51 & 63 & 60 & 86  & \\  84 & 94 & 9 & 75 & 19  & \\ \hline  454 & 314 & 218 & 369 & 299   & sum\ in\ ZZ\\  50 & 11 & 16 & 66 & 97 & sum\ in\ F_{101}\\  \end{array}
The five-element check is therefore:

c_1 = 50, c_2 = 11, c_3 = 16, c_4 = 66, c_5 = 97.
We transmit telegraphically the sequence of fifteen elements of F_{101}:

38 \quad  46\quad   00\quad   00 \quad  60\quad   08  \quad   00 \quad  00\quad   02\quad   99\quad   50  \quad   11\quad   16 \quad  66 \quad  97.
A discussion of possible errors will be given in another section. we simply note here that the $c_j$’s, as determined in the above tabulation, are:

c_1 = \sum_{i=1}^{10} a_i f_i,\quad   c_2 = \sum_{i=1}^{10} a_i^2 f_i,\quad   \dots, c_5 = \sum_{i=1}^{10} a_i^5 f_i.
If only a one-element check had been desired, we should have taken c_1=50, and a one-column tabulation would have sufficed. If a two-element check had been desired, we should have taken c_1=50, c_2=11 and a two-column tabulation would have sufficed. Etc.

If the operand sequence f_i contains less than 10 elements, the procedure, to determine check of Type A, is obvious. A q-element check upon f_1, f_2, \dots, f_{n}, with n<10, is as stated:

c_j = \sum_{i=1}^{10} a_i^j f_i,\ \ \ \ \ \ \ j = 1, 2, \dots, q,
with q=1,2,3,4,5. The manner of its evaluation, by means of Table 4, is clear.

Example 2: Check of Type B upon a sequence f_1, f_2, … , f_{8}.

Suppose that we desire a five-element check upon the numerical sequence 6500000000001794 – that is, upon

\begin{array}{cccccccc}  65  & 00  & 00  & 00 & 00  & 00  & 17  & 94\\  f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7 & f_8 \\  \end{array}
We wish to evaluate c_j = \sum_{i=1}^{8} b_i^j f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, 5). The tabulation is as follows:

\begin{array}{rrrrrl}  94 & 80 & 38  & 13  & 39  & row\ 1,\ Table\ 4,\ read:\ 94\ in\ column\ 65,\ etc. \\  90 & 19 & 59  & 45  & 60  &row\ 7,\ read:\ 90\ in\ column\ 17,\ etc.  \\  94 & 94 & 94 & 94 & 94  & \\ \hline  278 & 193 & 191 & 152 & 193   & sum\ in\ ZZ\\  76 & 92 & 90 & 51 & 92 & sum\ in\ F_{101}\\  c_1 & c_2 & c_3 & c_4 & c_5 & \\  \end{array}

Example 3: Check of Type A upon the same operand sequence as in Example 2.

We wish to evaluate c_j = \sum_{i=1}^{8} a_i^j f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, 5). The tabulation is as follows:

\begin{array}{rrrrrl}  94 & 80 & 38  & 13  & 39  & \\  90 & 19 & 59  & 45  & 60  &  \\  97 & 41 & 9 & 34 & 5  &row\ 8,\ Table\ 4,\ read:\ 97\ in\ col.\ 94,\ etc.  \\ \hline  281 & 140 & 106 & 92 & 104   & sum\ in\ ZZ\\  79 & 39 & 5 & 92 & 3 & sum\ in\ F_{101}\\  c_1 & c_2 & c_3 & c_4 & c_5 & \\  \end{array}

Example 4: Check of Type A and B upon the operand sequence

\begin{array}{ccccccc}  00  & 65  & 00  & 00  & 00 & 17  & 94\\  f_1 & f_2 & f_3 & f_4 & f_5 & f_6 & f_7  \\  \end{array}
We wish to evaluate

c_j = \sum_{i=1}^{7} a_i^j f_i= \sum_{i=1}^{7} b_i^j f_i,\ \ \ \ \ \ \ (j = 1, 2, \dots, 5).
The tabulation is as follows:

\begin{array}{rrrrrl}  58 & 30 & 19  & 76  & 1  & row\ 2,\ Table\ 4,\ read:\ 58\ in\ col.\ 65,\ etc. \\  21 & 20 & 96  & 77  & 6  &row\ 6,\ read:\ 21\ in\ col.\ 17,\ etc.  \\  58 & 10 & 47 & 29 & 5  &row\ 7,\ read:\ 58\ in\ col.\ 94,\ etc.  \\ \hline  137 & 60 & 162 & 182 & 12   & sum\ in\ ZZ\\  36 & 60 & 61 & 81 & 12 & sum\ in\ F_{101}\\  c_1 & c_2 & c_3 & c_4 & c_5 & \\  \end{array}

Questions of rigor will be discussed in a subsequent section. It may be noted here, however, that our checks make very
nice discriminations. Thus, although the operand sequence in Examples 3 and 4 are closely similar, the checking sequences are widely different.

It will now be apparent to those who are acquainted with the problems of code communication that we are in a position to furnish powerful and economical checks on message sequences in any conceivable telegraphic system. We have only to partition messages into groups of not more than ten, or not more that eight, elements each — according to any
definite prearrangement — and to check each group with a q-check, q=1,2,3,4,5 (as may be arranged), of Type A or of Type B. If it is desired to work with longer groups, we have only to enlarge Table 4. The limitations introduced in this paper may be largely overcome, or removed, by suitable amplification of the Table employed.

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

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 like this: [This is a comment. – wdj]. I used Sage (www.sagemath.org) to generate the tables in LaTeX.

Here is just the 13th section of his paper. I hope to post more later. (Part 12 is here.)


Reference matrices and table

We now turn our attention to the construction of reference matrices for checking in the field F_{101}. Our object is merely to give an account of problems arising. Hence the purposes of this paper will be served if we choose small illustrative matrices.

With

a_1 = 3, \ a_2 = 4, \ a_3 = 5, \ a_4 = 6, \ a_5 = 8, \ a_6 = 25, \ a_7 = 35, \ a_8 = 15, \ a_9 = 42, \ a_{10} = 1,

consider the reference matrix:

A = \left( \begin{array}{cccc} a_1 & a_2 & \dots & a_{10} \\ a_1^2 & a_2^2 & \dots & a_{10}^2 \\ \vdots & & & \vdots \\ a_1^5 & a_2^5 & \dots & a_{10}^5 \\ \end{array} \right) = \left(\begin{array}{rrrrrrrrrr} 3 & 4 & 5 & 6 & 8 & 25 & 35 & 15 & 42 & 1 \\ 9 & 16 & 25 & 36 & 64 & 19 & 13 & 23 & 47 & 1 \\ 27 & 64 & 24 & 14 & 7 & 71 & 51 & 42 & 55 & 1 \\ 81 & 54 & 19 & 84 & 56 & 58 & 68 & 24 & 88 & 1 \\ 41 & 14 & 95 & 100 & 44 & 36 & 57 & 57 & 60 & 1 \end{array}\right) .

A q-element check, q\leq 5, on the sequence f_1, f_2, \dots, f_n of n elements in F_{101}, n\leq 10, is given by

c_j = \sum_{i=1}^n a_i^j f_i,\ \ \ \ \ (j=1,2,\dots, q).
This check, being based upon the matrix A, will be called a check of “type A”.

With

b_1 = 3, \ b_2 = 4, \ b_3 = 5, \ b_4 = 6, \ b_5 = 8, \  b_6 = 25, \  b_7 = 35, \ b_8 = 1, \
consider the matrix:

B = \left(  \begin{array}{cccc}  b_1 & b_2 & \dots & b_{8} \\  b_1^2 & b_2^2 & \dots & b_{8}^2 \\  \vdots & & & \vdots \\  b_1^5 & b_2^5 & \dots & b_{8}^5 \\  \end{array}  \right)  =  \left(\begin{array}{rrrrrrrrrr}  3 & 4 & 5 & 6 & 8 & 25 & 35 & 1 \\  9 & 16 & 25 & 36 & 64 & 19 & 13 & 1 \\  27 & 64 & 24 & 14 & 7 & 71 & 51 & 1 \\  81 & 54 & 19 & 84 & 56 & 58 & 68 & 1 \\  41 & 14 & 95 & 100 & 44 & 36 & 57 & 1  \end{array}\right)
which is evidently a submatrix of $latex A$. We can obtain a $latex q$-element check, $latex q\leq 5$, on the sequence $latex f_1, f_2, \dots, f_n$, $latex n\leq 8$, taking

c_j = \sum_{i=1}^n b_i^j f_i,\ \ \ \ \ (j=1,2,\dots, q).
This check will be called a check of “type $latex B$”, since it is based upon the matrix $latex B$.

Table 4 below enables us to evaluate easily the checks of types A and B. Table 4 contains nine rows of one hundred columns each. [Note: I have omitted all but the first $14$ columns, for brevity. – wdj.] The ith row shows the products of all non-zero elements of F_{101} by a_i ($i=1,2,\dots, 9$), where the a_i‘s are given above.

\begin{array}{r|rrrrrrrrrrrrrrrrrrrrrrrr}    & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\ \hline  1 & 3 & 6 & 9 & 12 & 15 & 18 & 21 & 24 & 27 & 30 & 33 & 36 & 39 & 42 \\  2 & 4 & 8 & 12 & 16 & 20 & 24 & 28 & 32 & 36 & 40 & 44 & 48 & 52 & 56 \\  3 & 5 & 10 & 15 & 20 & 25 & 30 & 35 & 40 & 45 & 50 & 55 & 60 & 65 & 70 \\  4 & 6 & 12 & 18 & 24 & 30 & 36 & 42 & 48 & 54 & 60 & 66 & 72 & 78 & 84 \\  5 & 8 & 16 & 24 & 32 & 40 & 48 & 56 & 64 & 72 & 80 & 88 & 96 & 3 & 11 \\  6 & 25 & 50 & 75 & 100 & 24 & 49 & 74 & 99 & 23 & 48 & 73 & 98 & 22 & 47 \\  7 & 35 & 70 & 4 & 39 & 74 & 8 & 43 & 78 & 12 & 47 & 82 & 16 & 51 & 86 \\  8 & 15 & 30 & 45 & 60 & 75 & 90 & 4 & 19 & 34 & 49 & 64 & 79 & 94 & 8 \\  9 & 42 & 84 & 25 & 67 & 8 & 50 & 92 & 33 & 75 & 16 & 58 & 100 & 41 & 83 \\  \end{array}
Caption: A table of products with the a_i‘s.

Table 4 can be replaced by a highly convenient mechanical device, which greatly facilitates the rapid determination of the c_j‘s. But we are here only concerned with the mathematical description of checking operations, and not with devices to affect their practical application.

mathematics of party favors

True story: My wife bought a bunch of party favors for a family gathering. These were rolled up gift wrapping containing some cheap present. She opened on and found a party game labeled “The Mystery Calculator”. She gave it to me.

15927953450_07ec905b2d_o
This is what it is: A small folded cardboard mini-booklet of 6 cards of 4×8 arrays of numbers, ranging from 1 to 63.

Page 1:

\begin{array}{rrrrrrrr}  1 & 3 & 5 & 7 & 9 & 11 & 13 & 15 \\  17 & 19 & 21 & 23 & 25 & 27 & 29 & 31 \\  33 & 35 & 37 & 39 & 41 & 43 & 45 & 47 \\  49 & 51 & 53 & 55 & 57 & 59 & 61 & 63  \end{array}

Page 2:

\begin{array}{rrrrrrrr}  2 & 3 & 6 & 7 & 10 & 11 & 14 & 15 \\  18 & 19 & 22 & 23 & 26 & 27 & 30 & 31 \\  34 & 35 & 38 & 39 & 42 & 43 & 46 & 47 \\  50 & 51 & 54 & 55 & 58 & 59 & 62 & 63  \end{array}

Page 3:

\begin{array}{rrrrrrrr}  4 & 5 & 6 & 7 & 12 & 13 & 14 & 15 \\  20 & 21 & 22 & 23 & 28 & 29 & 30 & 31 \\  36 & 37 & 38 & 39 & 44 & 45 & 46 & 47 \\  52 & 53 & 54 & 55 & 60 & 61 & 62 & 63  \end{array}

Page 4:

\begin{array}{rrrrrrrr}  8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\  24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 \\  40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 \\  56 & 57 & 58 & 59 & 60 & 61 & 62 & 63  \end{array}

Page 5:

\begin{array}{rrrrrrrr}  16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 \\  24 & 25 & 26 & 27 & 28 & 29 & 30 & 31 \\  48 & 49 & 50 & 51 & 52 & 53 & 54 & 55 \\  56 & 57 & 58 & 59 & 60 & 61 & 62 & 63  \end{array}

Page 6:

\begin{array}{rrrrrrrr}  32 & 33 & 34 & 35 & 36 & 37 & 38 & 39 \\  40 & 41 & 42 & 43 & 44 & 45 & 46 & 47 \\  48 & 49 & 50 & 51 & 52 & 53 & 54 & 55 \\  56 & 57 & 58 & 59 & 60 & 61 & 62 & 63  \end{array}

Here are the rules to the game.

Show the 6 cards to a friend. Ask him or her secretly pick any number from any card. Tell them to look through the 6 cards and find those cards that the number they selected also appears, and give those cards to you. You add the numbers in the upper left-hand corner of these cards. This sum will be the number your friend selected.

I haven’t proven this works but my guess is that this is based on the mathematics of the Hamming code of length 6 (see this previous post and this one).

A curious conjecture about self-reciprocal polynomials

Let p be a polynomial
p(z) = a_0 + a_1z+\dots + a_nz^n\ \ \ \ \ \ a_i\in {\bf C},
and let p^* denote the reciprocal polynomial
p^*(z) = a_n + a_{n-1}z+\dots + a_0z^n=z^np(1/z).
We say p is self-reciprocal if p=p^*. For example,
1+2z+3z^2+2z^3+z^4
and
1+2z+3z^2+3z^3+2z^4+z^5
are self-reciprocal. Suppose
p(z) = a_0 + a_1z+\dots + a_dz^d+a_{d+1}z^{d+1}+a_dz^{d}+\dots +a_{1}z^{2d+1}+a_0z^{2d+2},\ \ \ \ \ \ a_i\in {\bf C},
or
p(z) = a_0 + a_1z+\dots + a_dz^d+a_{d+1}z^{d+1}+a_{d+1}z^{d+2}+a_dz^{d+3}+\dots +a_{1}z^{2d+2}+a_0z^{2d+3},\ \ \ \ \ \ a_i\in {\bf C},

The question is this: for which increasing sequences a_0<a_1<\dots a_{d+1} do the polynomial roots p(z)=0 lie on the unit circle |z|=1?

Some examples:

symmetric-increasing-coeff-plot1
This represents, when d=1 and a_0=1 and a_1=1.1 the largest a_{d+1} which has this roots property is as in the plot.

symmetric-increasing-coeff-plot2
This represents, when d=1 and a_0=1 and a_1=1.2 the largest a_{d+1} which has this roots property is as in the plot.

symmetric-increasing-coeff-plot3
This represents, when d=1 and a_0=1 and a_1=1.3 the largest a_{d+1} which has this roots property is as in the plot.

symmetric-increasing-coeff-plot4
This represents, when d=1 and a_0=1 and a_1=1.4 the largest a_{d+1} which has this roots property is as in the plot.

symmetric-increasing-coeff-plot5
This represents, when d=1 and a_0=1 and a_1=1.5 the largest a_{d+1} which has this roots property is as in the plot.

Conjecture 1: Let s:{\bf Z}_{>0}\to {\bf R}_{>0} be a ”slowly increasing” function.

  1. Odd degree case.
    If g(z)= a_0 + a_1z + \dots + a_dz^d, where a_i=s(i), then the roots of p(z)=g(z)+z^{d+1}g^*(z) all lie on the unit circle.
  2. Even degree case.
    The roots of
    p(z)=a_0 + a_1z + \dots + a_{d-1}z^{d-1} + a_{d}z^{d} + a_{d-1}z^{d+1} + \dots + a_{1}z^{2d-1}+a_0z^{2d}
    all lie on the unit circle.

The next conjecture gives an idea as to how fast a “slowly increasing” function can grow.

Conjecture 2:* Consider the even degree case only. The polynomial
p(z)=a_0 + a_1z + \dots + a_{d-1}z^{d-1} + a_{d}z^{d} + a_{d-1}z^{d+1} + \dots + a_{1}z^{2d-1}+a_0z^{2d}  ,
with a_0=1 and all a_i>0, is symmetric increasing if and only if it can be written as a product of quadratics of the form x^2-2\cos(\theta)x+1, where all but one of the factors satisfy 2\pi/4\leq \theta\leq 4\pi/3. One of the factors can be of the form x^2+\alpha x+1, for some \alpha \geq 0.

* It was pointed out to me by Els Withers that this conjecture is false.

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

The field F_{101}

All essential points connected with the checking of telegraphic sequences by the methods proposed in this paper may be fully illustrated in one finite field. For our purposes, perhaps the most useful field is F_{101}, to which we shall confine our attention in the following sections. The elements of the field F_{101} are the one hundred and one marks\footnote{Hill actually uses the symbol X in place of 100.} 0, 1, 2, \dots, 100. The operations of addition and multiplication are effected as explained in a previous example; and are abbreviated as suggested. To determine sums and products, we regard the marks of the field momentarily as integers of elementary arithmetic. Thus we have

\sum_1^n f_i = f_h,\ \ \ \ \ \ (\prod_1^n f_i = f_k),

the f_i being n marks of F_{101}, distinct or not, if, when the f_i are momentarily regarded as integers of elementary arithmetic, the congruence

\sum_1^n f_i \equiv f_h \pmod{101},\ \ \ \ \ \ (\prod_1^n f_i \equiv f_k \pmod{101}),

holds. It will not be possible to provide a full multiplication table for the field F_{101}. But the following special table will be found convenient.

\begin{array}{r|rrr} x & x^2 & 1/x & -x\\ 1 & 1 & 1 & 100 \\ 2 & 4 & 51 & 99 \\ 3 & 9 & 34 & 98 \\ 4 & 16 & 76 & 97 \\ 5 & 25 & 81 & 96 \\ 6 & 36 & 17 & 95 \\ 7 & 49 & 29 & 94 \\ 8 & 64 & 38 & 93 \\ 9 & 81 & 45 & 92 \\ 10 & 100 & 91 & 91 \\ 11 & 20 & 46 & 90 \\ 12 & 43 & 59 & 89 \\ 13 & 68 & 70 & 88 \\ 14 & 95 & 65 & 87 \\ 15 & 23 & 27 & 86 \\ 16 & 54 & 19 & 85 \\ 17 & 87 & 6 & 84 \\ 18 & 21 & 73 & 83 \\ 19 & 58 & 16 & 82 \\ 20 & 97 & 96 & 81 \\ 21 & 37 & 77 & 80 \\ 22 & 80 & 23 & 79 \\ 23 & 24 & 22 & 78 \\ 24 & 71 & 80 & 77 \\ 25 & 19 & 97 & 76 \\ 26 & 70 & 35 & 75 \\ 27 & 22 & 15 & 74 \\ 28 & 77 & 83 & 73 \\ 29 & 33 & 7 & 72 \\ 30 & 92 & 64 & 71 \\ 31 & 52 & 88 & 70 \\ 32 & 14 & 60 & 69 \\ 33 & 79 & 49 & 68 \\ \end{array}

\begin{array}{r|rrr} x & x^2 & 1/x & -x\\ 34 & 45 & 3 & 67 \\ 35 & 13 & 26 & 66 \\ 36 & 84 & 87 & 65 \\ 37 & 56 & 71 & 64 \\ 38 & 30 & 8 & 63 \\ 39 & 6 & 57 & 62 \\ 40 & 85 & 48 & 61 \\ 41 & 65 & 69 & 60 \\ 42 & 47 & 89 & 59 \\ 43 & 31 & 47 & 58 \\ 44 & 17 & 62 & 57 \\ 45 & 5 & 9 & 56 \\ 46 & 96 & 11 & 55 \\ 47 & 88 & 43 & 54 \\ 48 & 82 & 40 & 53 \\ 49 & 78 & 33 & 52 \\ 50 & 76 & 99 & 51 \\ 51 & 76 & 2 & 50 \\ 52 & 78 & 68 & 49 \\ 53 & 82 & 61 & 48 \\ 54 & 88 & 58 & 47 \\ 55 & 96 & 90 & 46 \\ 56 & 5 & 92 & 45 \\ 57 & 17 & 39 & 44 \\ 58 & 31 & 54 & 43 \\ 59 & 47 & 12 & 42 \\ 60 & 65 & 32 & 41 \\ 61 & 85 & 53 & 40 \\ 62 & 6 & 44 & 39 \\ 63 & 30 & 93 & 38 \\ 64 & 56 & 30 & 37 \\ 65 & 84 & 14 & 36 \\ 66 & 13 & 75 & 35 \\ \end{array}

\begin{array}{r|rrr} x & x^2 & 1/x & -x\\ 67 & 45 & 98 & 34 \\ 68 & 79 & 52 & 33 \\ 69 & 14 & 41 & 32 \\ 70 & 52 & 13 & 31 \\ 71 & 92 & 37 & 30 \\ 72 & 33 & 94 & 29 \\ 73 & 77 & 18 & 28 \\ 74 & 22 & 86 & 27 \\ 75 & 70 & 66 & 26 \\ 76 & 19 & 4 & 25 \\ 77 & 71 & 21 & 24 \\ 78 & 24 & 79 & 23 \\ 79 & 80 & 78 & 22 \\ 80 & 37 & 24 & 21 \\ 81 & 97 & 5 & 20 \\ 82 & 58 & 85 & 19 \\ 83 & 21 & 28 & 18 \\ 84 & 87 & 95 & 17 \\ 85 & 54 & 82 & 16 \\ 86 & 23 & 74 & 15 \\ 87 & 95 & 36 & 14 \\ 88 & 68 & 31 & 13 \\ 89 & 43 & 42 & 12 \\ 90 & 20 & 55 & 11 \\ 91 & 100 & 10 & 10 \\ 92 & 81 & 56 & 9 \\ 93 & 64 & 63 & 8 \\ 94 & 49 & 72 & 7 \\ 95 & 36 & 84 & 6 \\ 96 & 25 & 20 & 5 \\ 97 & 16 & 25 & 4 \\ 98 & 9 & 67 & 3 \\ 99 & 4 & 50 & 2 \\ 100 & 1 & 100 & 1 \end{array}

Squares, reciprocals, negatives

Using the scheme of reciprocals shown in this Table, we may easily perform an rational operations in F_{101}.

Example:

Suppose, for example, that we wish to solve the system of equations:

36x-79y=52,\ \ \ 90x+85y = 98.

They may be written

x-79y/36 = 13/9,\ \ \ \ x+17y/18 = 49/45

and the fractions are quickly evaluated. Thus: -79/36 = 96. Determining the fractions in this manner, we write the two equations in the form:

x+96y=80,\ \ \ \ x+29y=37,

whence y=73 and x=41

The modulus 101 is very convenient to work with. The residue, modulo 101, of any integer is immediately obvious, at sight of the integer, and is therefore obtained without computation.

The trouble with college math classes …

Ran across this terrific observation in Wallace’s book on set theory and mathematics, and thought I’d share:

The trouble with college math classes – which classes consist almost entirely in the rhythmic ingestion and regurgitation of abstract information, and are paced in such a way as to maximize this reciprocal data-flow – is that their shear surface-level difficulty can fool us into thinking we really know something when all we really “know” is abstract formulas and rules for their deployment. Rarely do math classes ever tell us if a formula is truely significant, or why, or where it came from, or what was at stake.


David Foster Wallace at the Hammer Museum in Los Angeles, January 2006. 2006 CC BY-SA 3.0

And, of course, rarely do students think to ask – the formulas alone take so much work to “understand” (i.e., be able to solve problems correctly with), we often aren;t aware that we don’t understand them at all. That we end up not even knowing that we don’t know if the most incidious part of most math classes.

– David Foster Wallace, in Everything and More (section 2a)